https://www.luogu.org/problemnew/show/P3295
最近对省选题充满敬畏之心
先想30分暴力：对于一组相等的关系，我们用并查集表示哪些数需要相等，如果相等就放在一个集合里，最后统计答案就9 * 10 ^ (集合个数-1）
这样就是O(n^2)的
正解是看了题解想出来的，不然真的没辙
考虑维护f[i][j]:i->i + 2 ^ j - 1的数的实际编号，最后编号相同的数就算作一个集合
那么我们最后要知道每个数的编号来统计集合个数，因此在一开始给每个f[i][j]都赋一个初始编号，最后合并的时候从大到小合并，最后统计每个f[i][0]即可
显然的，如果f[i][j]和f[s][t]的区间编号相同，那么他们对应的子区间f[i][j - 1],f[s][t - 1]和f[i + (1 << j - 1)][j - 1],f[s + (1 << t - 1)][t - 1]对应相等
问题来了，我们枚举i，j，哪儿来的s，t啊，这该怎么转移？？？
我们一开始给每个f[i][j]=++cnt的时候，都记录编号为cnt的序列的起始位置
这样在枚举i,j时，就可以找到原数列中和f[i][j]应对应相等的部分，进行合并即可
复杂度O(nlogn)
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } typedef long long ll; const int maxn = 1e5 + 5; const ll mod = 1e9 + 7; int n,m; int par[maxn * 20]; inline void init(int n) { for(int i = 1;i <= n;i++) par[i] = i; } int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } inline void merge(int x,int y) { x = find(x),y = find(y); if(x < y) swap(x,y); par[x] = y; } int f[maxn * 20][21],cnt,st[maxn * 20]; int main() { n = read(),m = read(); init((maxn - 5) * 20); for(int j = 20;j >= 0;j--) for(int i = 1;i + (1 << j) - 1 <= n;i++) f[i][j] = ++cnt,st[cnt] = i; for(int i = 1;i <= m;i++) { int l1 = read(),r1 = read(),l2 = read(),r2 = read(); for(int j = 20;j >= 0;j--) if(r1 - l1 + 1 - (1 << j) >= 0) merge(f[l1][j],f[l2][j]),l1 += 1 << j,l2 += 1 << j; } for(int j = 20;j >= 1;j--) for(int i = 1;i + (1 << j) - 1<= n;i++) { int s = st[find(f[i][j])]; merge(f[i][j - 1],f[s][j - 1]); merge(f[i + (1 << (j - 1))][j - 1],f[s + (1 << (j - 1))][j - 1]); } ll ans = 9; bool flag =0; for(int i = 1;i <= n;i++) if(par[f[i][0]] == f[i][0] && flag) ans = ans * 1ll * 10 % mod; else if(par[f[i][0]] == f[i][0]) flag = 1; printf("%lld",ans); }