题意：N个点M条边的无向图，q次询问保留图中编号在[l,r]的边的时候图中的联通块个数。
询问加密，强制在线
n,m,q<=200000
题意：RYZ作业
以下转载自hzwer http://hzwer.com/4358.html 本人实力有限难以清晰描述
有一个比较猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：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，我反正是用的函数式线段树
话说LCT自带十倍常数 被卡了一天半 最后还是把swap和isroot拆出来才卡过的……
var t,c:array[..,..]of longint;
mx,a,b,rev,fa,root,q:array[..]of longint;
x,y:array[..]of longint;
n,m,cnt,i,k,tp,tmp,lastans,l,r,top,tt:longint; {function isroot(x:longint):boolean;
begin
if (t[fa[x],0]<>x)and(t[fa[x],1]<>x) then exit(true);
exit(false);
end;
}
{procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; } procedure pushup(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
mx[x]:=x;
if b[mx[l]]<b[mx[x]] then mx[x]:=mx[l];
if b[mx[r]]<b[mx[x]] then mx[x]:=mx[r];
end; procedure pushdown(x:longint);
var l,r:longint;
begin
l:=t[x,]; r:=t[x,];
if rev[x]> then
begin
rev[x]:=rev[x] xor ; rev[l]:=rev[l] xor ; rev[r]:=rev[r] xor ;
// swap(t[x,],t[x,]);
tt:=t[x,]; t[x,]:=t[x,]; t[x,]:=tt;
end;
end; procedure rotate(x:longint);
var y,z,l,r:longint;
begin
y:=fa[x]; z:=fa[y];
if t[y,]=x then l:=
else l:=;
r:=l xor ;
// if not isroot(y) then
if (t[fa[y],]=y)or(t[fa[y],]=y) then
begin
if t[z,]=y then t[z,]:=x
else t[z,]:=x;
end;
fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
t[y,l]:=t[x,r]; t[x,r]:=y;
pushup(y);
pushup(x);
end; procedure splay(x:longint);
var y,z,k:longint;
begin
inc(top); q[top]:=x;
k:=x;
// while not isroot(k) do
while (t[fa[k],]=k)or(t[fa[k],]=k) do
begin
inc(top); q[top]:=fa[k];
k:=fa[k];
end;
while top> do
begin
pushdown(q[top]);
dec(top);
end; // while not isroot(x) do
while (t[fa[x],]=x)or(t[fa[x],]=x) do
begin
y:=fa[x]; z:=fa[y];
//if not isroot(y) then
if (t[fa[y],]=y)or(t[fa[y],]=y) then
begin
if (t[y,]=x)xor(t[z,]=y) then rotate(x)
else rotate(y);
end;
rotate(x);
end;
end; procedure access(x:longint);
var last:longint;
begin
last:=;
while x> do
begin
splay(x); t[x,]:=last; pushup(x);
last:=x; x:=fa[x];
end;
end; function findroot(x:longint):longint;
var k:longint;
begin
access(x); splay(x);
k:=x;
while t[k,]<> do k:=t[k,];
exit(k);
end; procedure makeroot(x:longint);
begin
access(x); splay(x); rev[x]:=rev[x] xor ;
end; procedure link(x,y:longint);
begin
makeroot(x); fa[x]:=y;
end; procedure cut(x,y:longint);
begin
makeroot(x); access(y); splay(y); t[y,]:=; fa[x]:=;
end; procedure update(l,r:longint;var p:longint;x:longint);
var mid:longint;
begin
inc(cnt); c[cnt]:=c[p];
p:=cnt; inc(c[p,]);
if l=r then exit;
mid:=(l+r)>>;
if x<=mid then update(l,mid,c[p,],x)
else update(mid+,r,c[p,],x);
end; function query(p1,p2,l,r,x:longint):longint;
var mid:longint;
begin
if r=x then exit(c[p2,]-c[p1,]);
mid:=(l+r)>>;
if x<=mid then exit(query(c[p1,],c[p2,],l,mid,x))
else exit(c[c[p2,],]-c[c[p1,],]+query(c[p1,],c[p2,],mid+,r,x));
end; begin
assign(input,'data.in'); reset(input);
assign(output,'bzoj3514.out'); rewrite(output);
readln(n,m,k,tp);
fillchar(b,sizeof(b),$1f);
for i:= to m do
begin
readln(x[i],y[i]);
if x[i]=y[i] then a[i]:=i
else
begin
if findroot(x[i])=findroot(y[i]) then
begin
makeroot(x[i]); access(y[i]); splay(y[i]);
tmp:=mx[y[i]];
a[i]:=tmp-n;
cut(x[tmp-n],tmp); cut(tmp,y[tmp-n]);
b[n+i]:=i; mx[n+i]:=n+i;
link(x[i],i+n); link(i+n,y[i]);
end
else
begin
b[n+i]:=i; mx[n+i]:=n+i;
link(x[i],i+n); link(i+n,y[i]);
end;
end; end;
//for i:= to m do writeln(a[i]);
for i:= to m do
begin
root[i]:=root[i-];
update(,m,root[i],a[i]);
end;
for i:= to k do
begin
readln(l,r);
if tp= then
begin
l:=l xor lastans;
r:=r xor lastans;
end;
lastans:=n-query(root[l-],root[r],,m,l-);
writeln(lastans);
end; close(input);
close(output);
end.