hentai。。。
原题：
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
对于100%的数据，1≤N、M、K≤200,000。
直接复制wulala的题解
wulala
葱娘说这是一个很巧妙的题。。
有一个比较猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;
这个显然是可以用LCT来弄的对吧。
然后对于每个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值
正确性可以YY一下：
如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献
反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1
对于查询从l ~ r中有多少边的ntr小于l，我反正是用的函数式线段树
好妙啊
ntr。。。真是hentai，让我传承传承了hentai的po姐美好的意境吧
这题我写了一下午
T？WA我也认了T什么鬼啊
然后找rxz要来70M的数据。。。
突然想起来有些点是强制在线的，然后感觉就是我WA了
但是我把不强制在线的数据跑一下答案没错啊？
又从头到尾查一下，找不到毛病啊？
然后gdb，跟踪到第一个数据的时候……
一拍脑袋，发现last_ans没设初值。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int inf=(int)1e9;
int rd(){int z=; char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z;
}
struct edg{int x,y;}e[];
int n,m,o,mk;
int fth[],chd[][],v[],mnv[],rvs[];
int stck[],tp=;
int ntr[],c[];
int w[],cwd[][],rts[],ndc=;
inline bool isrt(int x){ return (chd[fth[x]][]!=x)&(chd[fth[x]][]!=x);}
inline void pshu(int x){ mnv[x]=min(v[x],min(mnv[chd[x][]],mnv[chd[x][]]));}
inline void pshd(int x){
if(!rvs[x]) return ;
rvs[chd[x][]]^=,rvs[chd[x][]]^=,rvs[x]=;
swap(chd[x][],chd[x][]);
}
void rtt(int x){
int y=fth[x],z=fth[fth[x]],l,r;
r=(chd[y][]==x); l=r^;
if(!isrt(y)) chd[z][chd[z][]==y]=x;
fth[x]=z,fth[y]=x,fth[chd[x][r]]=y;
chd[y][l]=chd[x][r],chd[x][r]=y;
pshu(y),pshu(x);
}
void sply(int x){
stck[tp=]=x;
for(int i=x;!isrt(i);i=fth[i]) stck[++tp]=fth[i];
while(tp) pshd(stck[tp--]);
while(!isrt(x)){
if(!isrt(fth[x])) rtt((chd[fth[x]][]==x)^(chd[fth[fth[x]]][]==fth[x])?x:fth[x]);
rtt(x);
}
}
inline void accs(int x){ for(int i=;x;sply(x),chd[x][]=i,pshu(x),x=fth[i=x]);}
inline void qdrt(int x){ accs(x),sply(x),rvs[x]^=;}
inline void ct(int x,int y){ qdrt(x),accs(y),sply(y),chd[y][]=fth[x]=;}
inline void lk(int x,int y){ qdrt(x),fth[x]=y,sply(x);}
inline int gtrt(int x){ while(fth[x]) x=fth[x]; return x;}
inline int sch(int x,int y){ qdrt(x),accs(y),sply(y); return mnv[y];}
void ist(int x){
if(e[x].x==e[x].y){ ntr[x]=x; return ;}
if(gtrt(e[x].x)==gtrt(e[x].y)){
ntr[x]=sch(e[x].x,e[x].y);
ct(n+ntr[x],e[ntr[x]].x),ct(n+ntr[x],e[ntr[x]].y);
mnv[n+ntr[x]]=inf;
}
mnv[n+x]=v[n+x]=x;
lk(n+x,e[x].x),lk(n+x,e[x].y);
}
/*int bnrsch(int x){
int l=1,r=m,md;
while(l+1<r) md=(l+r)>>1,(c[md]>=x ? l : r)=md;
return c[md]==l ? l : r;
}*/
int gtsgmttr(int l,int r){
int x=++ndc,md=(l+r)>>;
if(l!=r) cwd[x][]=gtsgmttr(l,md),cwd[x][]=gtsgmttr(md+,r);
return x;
}
int mdf(int x,int l,int r,int y,int z){
w[++ndc]=w[x],cwd[ndc][]=cwd[x][],cwd[ndc][]=cwd[x][],x=ndc;
if(l==r){ w[x]+=z; return x;}
int md=(l+r)>>;
if(y<=md) cwd[x][]=mdf(cwd[x][],l,md,y,z);
else cwd[x][]=mdf(cwd[x][],md+,r,y,z);
w[x]=w[cwd[x][]]+w[cwd[x][]];
return x;
}
int qur(int x,int l,int r,int ql,int qr){
if(l==ql && r==qr) return w[x];
int md=(l+r)>>;
if(ql<=md && qr>md) return qur(cwd[x][],l,md,ql,md)+qur(cwd[x][],md+,r,md+,qr);
else if(qr<=md) return qur(cwd[x][],l,md,ql,qr);
else return qur(cwd[x][],md+,r,ql,qr);
}
int main(){//freopen("ddd.in","r",stdin);
//freopen("ddd.out","w",stdout);
int l,r,lst;
cin>>n>>m>>o>>mk;
fill(mnv,mnv+m+n+,inf),fill(v,v+m+n+,inf);
for(int i=;i<=m;++i) e[i].x=rd(),e[i].y=rd(),ist(i);
/*for(int i=1;i<=m;++i) c[i]=ntr[i];
sort(c+1,c+m+1);
for(int i=1;i<=m;++i) ntr[i]=bnrsch(ntr[i]);*/
rts[]=gtsgmttr(,m);
for(int i=;i<=m;++i) rts[i]=mdf(rts[i-],,m,ntr[i],);
lst=;
for(int i=;i<=o;++i){
l=rd()^(mk*lst),r=rd()^(mk*lst);
printf("%d\n",lst=n-qur(rts[r],,m,,l-)+qur(rts[l-],,m,,l-));
}
return ;
}