考虑暴力的做法：每次输入相当于指定两个区间相等，对每个位置建立一个节点，每次两个区间相等相当于若干组两两相等，用并查集维护即可。这样的时间复杂度是O(n^2)。 考虑延迟修改：对于一段区间，拆分成若干2^i长的小区间，然后直接让两个小区间相等。这样每次只要修改logn个小区间即可。最后把这nlogn个区间从大到小分解，就得到了n个最小区间（就是每个数）的相等关系。设并查集中树的个数为num（相当于有多少组可以不同的区间），则答案为9*10^(num-1)，因为不能有前导0。时间复杂度O(nlogn)。 具体时间就是用ST表跑倍增了，这个延迟修改非常巧妙啊。注意特判n=1是是允许最高位为0的。
#include<cmath> #include<cstdio> #include<vector> #include <queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 200000 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; int fa[N*20],id[N][20],d[N*20][2]; int pw[20]; int n,m,i,j,tot,l1,l2,r1,r2,k,s,t,cnt; ll res; int getfa(int x) {return fa[x]?fa[x]=getfa(fa[x]):x;} int merge(int x,int y) { x = getfa(x); y = getfa(y); if (x != y) fa[y] = x; } int main() { pw[0] = 1; fo(i,1,18) pw[i] = pw[i-1]*2; scanf("%d%d",&n,&m); if (n == 1) {cout<<10<<endl; return 0;} fo(i,1,n) fo(j,0,18) {id[i][j] = ++tot; d[tot][0] = i; d[tot][1] = j;} fo(i,1,m) { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); fd(j,18,0) if (l1+pw[j]-1<=r1) { merge(id[l1][j],id[l2][j]); l1 += pw[j]; l2 += pw[j]; } } fd(j,18,1) fo(i,1,n) { k = getfa(id[i][j]); s = d[k][0]; t = d[k][1]; merge(id[i][j-1],id[s][t-1]); merge(id[i+pw[j-1]][j-1],id[s+pw[t-1]][t-1]); } fo(i,1,n) if (!fa[id[i][0]]) cnt++; res = 9; fo(i,1,cnt-1) res = (ll)(res * 10) % (1000000007); printf("%lld",res); return 0; }