考虑使用LCT维护时间最大生成树，那么对于第(i)条边，其加入时可能会删去一条边。记(pre_i)表示删去的边的编号，如果不存在则(pre_i = 0)，如果是自环则(pre_i = i)。
因为连通块数量等于点数减树边数量，而对于一组询问([l,r])，当(pre_i < l leq i leq r)的时候就会在这张图上额外增加一条树边。所以我们只需要使用主席树做一个二维数点就可以了。
时空复杂度(O(nlogn))
#include<bits/stdc++.h>
using namespace std;
int read(){
int a = 0; char c = getchar(); bool f = 0;
while(!isdigit(c)){f = c == '-'; c = getchar();}
while(isdigit(c)){
a = a * 10 + c - 48; c = getchar();
}
return f ? -a : a;
}
const int _ = 4e5 + 7;
namespace segt{
const int __ = _ * 30;
int sum[__] , lch[__] , rch[__] , cnt;
#define mid ((l + r) >> 1)
void modify(int &x , int l , int r , int tar){
int t = ++cnt; sum[t] = sum[x] + 1; lch[t] = lch[x]; rch[t] = rch[x]; x = t;
if(l == r) return;
mid >= tar ? modify(lch[x] , l , mid , tar) : modify(rch[x] , mid + 1 , r , tar);
}
int qry(int x , int l , int r , int L , int R){
if(!x || l >= L && r <= R) return sum[x];
int sum = 0;
if(mid >= L) sum = qry(lch[x] , l , mid , L , R);
if(mid < R) sum += qry(rch[x] , mid + 1 , r , L , R);
return sum;
}
}using segt::modify; using segt::qry;
namespace LCT{
int fa[_] , ch[_][2] , val[_] , mn[_]; bool rmrk[_];
bool nroot(int x){return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}
bool son(int x){return ch[fa[x]][1] == x;}
void up(int x){mn[x] = min(min(ch[x][0] ? mn[ch[x][0]] : (int)1e9 , ch[x][1] ? mn[ch[x][1]] : (int)1e9) , val[x]);}
void mark(int x){rmrk[x] ^= 1; swap(ch[x][0] , ch[x][1]);}
void down(int x){if(rmrk[x]){mark(ch[x][0]); mark(ch[x][1]); rmrk[x] = 0;}}
void dall(int x){if(nroot(x)) dall(fa[x]); down(x);}
void rot(int x){
bool f = son(x); int y = fa[x] , z = fa[y] , w = ch[x][f ^ 1];
fa[x] = z; if(nroot(y)) ch[z][son(y)] = x;
fa[y] = x; ch[x][f ^ 1] = y;
ch[y][f] = w; if(w) fa[w] = y;
up(y);
}
void splay(int x){
dall(x);
while(nroot(x)){
if(nroot(fa[x])) rot(son(fa[x]) == son(x) ? fa[x] : x);
rot(x);
}
up(x);
}
void access(int x){for(int y = 0 ; x ; y = x , x = fa[x]){splay(x); ch[x][1] = y; if(y) fa[y] = x; up(x);}}
void mkrt(int x){access(x); splay(x); mark(x);}
void split(int x , int y){mkrt(x); access(y); splay(y);}
void link(int x , int y){mkrt(x); fa[x] = y;}
void cut(int x , int y){split(x , y); ch[y][0] = fa[x] = 0; up(y);}
int fdrt(int x){access(x); splay(x); while(down(x) , ch[x][0]) x = ch[x][0]; splay(x); return x;}
}using namespace LCT;
int rt[_] , pre[_] , s[_] , t[_] , N , M , K , TP , lastans;
int main(){
N = read(); M = read(); K = read(); TP = read();
for(int i = 1 ; i <= M ; ++i){
s[i] = read() , t[i] = read(); LCT::val[i + N] = LCT::mn[i + N] = i;
}
for(int i = 1 ; i <= N ; ++i) LCT::val[i] = LCT::mn[i] = 1e9;
for(int i = 1 ; i <= M ; ++i)
if(s[i] != t[i]){
if(fdrt(s[i]) == fdrt(t[i])){
split(s[i] , t[i]); int id = mn[t[i]];
pre[i] = id; cut(s[id] , id + N); cut(t[id] , id + N);
}
link(s[i] , i + N); link(t[i] , i + N);
}
else pre[i] = i;
for(int i = 1 ; i <= M ; ++i) segt::modify(rt[i] = rt[i - 1] , 0 , M , pre[i]);
for(int i = 1 ; i <= K ; ++i){
int l = read() ^ (TP * lastans) , r = read() ^ (TP * lastans);
printf("%d
" , lastans = N - (segt::qry(rt[r] , 0 , M , 0 , l - 1) - (l - 1)));
}
return 0;
}