一个朴素的做法就是暴力连边并查集，可是这是\(O(n^2)\)的。发现每一次连边可以看成两个区间覆盖，这两个区间之间一一对应地连边。可线段树对应的两个节点的size可能不同，这会导致“一一对应”的条件在线段树上失效。所以我们需要使用ST表来完成连边。
对原序列建好ST表，对于每一个修改将两个区间覆盖到ST表上然后两两之间连边。注意在ST表上连边的两个区间要对应，即如果ST表上对应\([l,r]\)的区间与对应\([L,R]\)的区间连了边，意味着对于\(\forall i \in [0 , r - l],\)有边\((l + i , L + i)\)。
这样连边的复杂度是\(O(nlogn)\)的，但是查询就比较麻烦了，因为我们并查集只能查询大小为\(1\)的区间，而不能混入这些奇奇怪怪的区间。
但是我们可以把每一层ST表对应的并查集向下传，直到传到最底层。具体来说从上往下遍历每一层ST表对应的并查集，找到第\(i\)个点和它在这一层并查集上的根。这两个点在下一层的ST表中分别对应两个点，而连边的时候又是对应的，所以将它们的左儿子之间连边、右儿子之间连边即可。
总复杂度\(O(nlogn)\)
#include#include #include #include //This code is written by Itstusing namespace std;inline int read(){ int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return a;}const int MAXN = 100007 , MOD = 1e9 + 7;int ST[19][MAXN];int N , M , cnt , logN , head[MAXN << 3] , dir[MAXN * 20] , fa[MAXN * 20];void init(){ for(logN = 0 ; 1 << logN <= N ; ++logN) for(int j = 1 ; j + (1 << logN) - 1 <= N ; ++j){ ST[logN][j] = ++cnt; dir[cnt] = j; fa[cnt] = cnt; } --logN;}int find(int a){return fa[a] == a ? a : (fa[a] = find(fa[a]));}void merge(int a , int b){fa[find(a)] = find(b);}inline void add(int a , int b , int len){ for(int i = 18 ; i >= 0 ; --i) if(len & (1 << i)){ merge(ST[i][a] , ST[i][b]); a += 1 << i; b += 1 << i; }}int main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); //freopen("out","w",stdout);#endif N = read(); M = read(); init(); for(int i = 1 ; i <= M ; ++i){ int a = read() , b = read() , c = read(); read(); add(a , c , b - a + 1); } for(int i = logN ; i ; --i) for(int j = 1 ; j + (1 << i) - 1 <= N ; ++j){ int t = find(ST[i][j]); if(t != ST[i][j]){ int x = dir[t]; merge(ST[i - 1][j] , ST[i - 1][x]); merge(ST[i - 1][j + (1 << i - 1)] , ST[i - 1][x + (1 << i - 1)]); } } bool f = 0; int ans = 1; for(int i = 1 ; i <= N ; ++i) if(fa[i] == i){ ans = ans * (9ll + f) % MOD; f = 1; } cout << ans; return 0;}