N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

 K行每行一个整数代表该组询问的联通块个数。

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cmath>
  6 #include <string>
  7 #include <cstring>
  8 #include <algorithm>
  9 #define MIN(a,b) (a<b?a:b)
 10 #define RG register
 11 const int N = 500000;
 12 const int M = 15000000;
 13 const int inf = 2147483641;
 14 
 15 using namespace std;
 16 
 17 int gi(){
 18     RG char ch=getchar();RG int x=0;
 19     while(ch<‘0‘ || ch>‘9‘) ch=getchar();
 20     while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
 21     return x;
 22 }
 23 
 24 int fa[N],c[2][N],rev[N],st[N],lt[N],mn[N],a[N],b[N],rt[N];
 25 int n,m,k,type,cnt;
 26 
 27 struct date{
 28     int l,r,s;
 29 }tr[M];
 30 
 31 int isroot(int x){
 32     return c[0][fa[x]]!=x && c[1][fa[x]]!=x;
 33 }
 34 
 35 void pushdown(int x){
 36     if (rev[x]==0) return;
 37     rev[x]^=1,rev[c[0][x]]^=1,rev[c[1][x]]^=1;
 38     swap(c[0][x],c[1][x]);
 39     return;
 40 }
 41 
 42 void update(int x){
 43     mn[x]=x<=n?inf:x;
 44     mn[x]=MIN(mn[x],MIN(mn[c[0][x]],mn[c[1][x]]));
 45     return;
 46 }
 47 
 48 void rotate(int x){
 49     int l,r,y=fa[x],z=fa[y];
 50     if (c[0][y]==x) l=0;
 51     else l=1;r=l^1;
 52     if (!isroot(y))
 53         if (c[0][z]==y) c[0][z]=x;
 54         else c[1][z]=x;
 55     fa[x]=z,fa[y]=x,fa[c[r][x]]=y;
 56     c[l][y]=c[r][x],c[r][x]=y;
 57     update(y),update(x);
 58     return;
 59 }
 60 
 61 void splay(int x){
 62     int tot=0;st[++tot]=x;
 63     for (RG int i=x; !isroot(i); i=fa[i]) st[++tot]=fa[i];
 64     for (RG int i=tot; i; --i) pushdown(st[i]);
 65     while(!isroot(x)){
 66         int y=fa[x],z=fa[y];
 67         if (!isroot(y))
 68             if (c[0][y]==x ^ c[0][z]==y) rotate(x);
 69             else rotate(y);
 70         rotate(x);
 71     }
 72     return;
 73 }
 74 
 75 void access(int x){
 76     int t=0;
 77     while(x){
 78         splay(x);
 79         c[1][x]=t;update(x);
 80         t=x,x=fa[x];
 81     }
 82     return;
 83 }
 84 
 85 void rever(int x){
 86     access(x),splay(x),rev[x]^=1;
 87     return;
 88 }
 89 
 90 void link(int l,int r){
 91     rever(l),fa[l]=r;
 92     return;
 93 }
 94 
 95 void cut(int l,int r){
 96     rever(l),access(r),splay(r);
 97     c[0][r]=fa[l]=0;
 98     return;
 99 }
100 
101 int query(int x){
102     access(x),splay(x);
103     while(c[0][x]) x=c[0][x];
104     return x;
105 }
106 
107 void build(int &t,int l,int r,int s){
108     tr[++cnt]=tr[t];t=cnt;
109     ++tr[t].s;
110     if (l==r) return;
111     int mid=(l+r)>>1;
112     if (s<=mid) build(tr[t].l,l,mid,s);
113     else build(tr[t].r,mid+1,r,s);
114     return;
115 }
116 
117 int query(int x,int l,int r,int ql,int qr){
118     if (ql>qr) return 0;
119     if (ql<=l && r<=qr) return tr[x].s;
120     int ans=0,mid=(l+r)>>1;
121     if (ql<=mid) ans+=query(tr[x].l,l,mid,ql,qr);
122     if (qr>mid) ans+=query(tr[x].r,mid+1,r,ql,qr);
123     return ans;
124 }
125 
126 int main(){
127     freopen("splay.in","r",stdin);
128     freopen("splay.out","w",stdout);
129     n=gi(),m=gi(),k=gi(),type=gi();
130     for (RG int i=0; i<=n; ++i) mn[i]=inf;
131     for (RG int i=1; i<=m; ++i){
132         int l=gi(),r=gi();
133         if (l==r) {lt[i]=m;continue;}
134         a[i]=l,b[i]=r;
135         if (query(l)==query(r)){
136             rever(l),access(r),splay(r);
137             int z=a[mn[r]-n],y=b[mn[r]-n],k=mn[r];
138             lt[i]=mn[r]-n;
139             cut(z,k),cut(k,y);
140         }
141         link(l,i+n),link(i+n,r);
142     }
143     for (RG int i=1; i<=m; ++i){
144         int g=lt[i];
145         rt[i]=rt[i-1];
146         build(rt[i],0,m,g);
147     }
148     int jl=0;
149     for (RG int i=1; i<=k; ++i){
150         int l=gi()^jl,r=gi()^jl,ans=n;
151         ans-=query(rt[r],0,m,0,l-1)-query(rt[l-1],0,m,0,l-1);
152         printf("%d\n",ans);
153         if (type) jl=ans;
154     }
155     return 0;
156 }