3514: Codechef MARCH14 GERALD07加强版
Time Limit: 60 Sec Memory Limit: 256 MB
Submit: 2177 Solved: 834
[Submit][Status][Discuss]Description
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
Input
第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。Output
K行每行一个整数代表该组询问的联通块个数。
Sample Input
3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2Sample Output
2
1
3
1HINT
对于100%的数据，1≤N、M、K≤200,000。
2016.2.26提高时限至60s
Source
用LCT求出NTR数组，然后主席树在线查询即可，比较简洁巧妙。
不过是两个高级数据结构合在一起，而且不是嵌套，理论上很好写。
实际上犯了很多低级错误，而且非常难调，以后一定要慢点写代码。
#include<cstdio>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=,K=,M=,inf=;
int n,m,Q,op,l,r,x,u,v,nd,ans,fa[N],ntr[K],root[K];
struct E{ int u,v; }e[K];
int find(int x){ return (fa[x]==x) ? x : fa[x]=find(fa[x]); } struct LCT{
int v[N],mn[N],s[N],ch[N][],f[N],tag[N];
bool isroot(int x){ return (!f[x]) || ((ch[f[x]][]!=x) && (ch[f[x]][]!=x)); }
void rev(int x){ swap(ch[x][],ch[x][]); tag[x]^=; }
void push(int x){ if (tag[x]) rev(lc),rev(rc),tag[x]=; }
void pd(int x){ if (!isroot(x)) pd(f[x]); push(x); } void upd(int x){
mn[x]=x;
if (v[mn[lc]]<v[mn[x]]) mn[x]=mn[lc];
if (v[mn[rc]]<v[mn[x]]) mn[x]=mn[rc];
} void rot(int x){
int y=f[x],z=f[y],w=ch[y][]==x;
if (!isroot(y)) ch[z][ch[z][]==y]=x;
f[x]=z; f[y]=x; f[ch[x][w^]]=y;
ch[y][w]=ch[x][w^]; ch[x][w^]=y; upd(y);
} void splay(int x){
pd(x);
while (!isroot(x)){
int y=f[x],z=f[y];
if (!isroot(y)){ if ((ch[z][]==y)^(ch[y][]==x)) rot(x); else rot(y); }
rot(x);
}
upd(x);
} void access(int x){ for (int y=; x; y=x,x=f[x]) splay(x),ch[x][]=y,upd(x); }
void mkroot(int x){ access(x); splay(x); rev(x);}
void link(int x,int y){ mkroot(x); f[x]=y; }
void cut(int x,int y){ mkroot(x); access(y); splay(y); ch[y][]=f[x]=; upd(y); }
int que(int x,int y){ mkroot(x); access(y); splay(y); return mn[y]; }
}T; struct S{
int ls[M],rs[M],sm[M]; void ins(int y,int &x,int L,int R,int pos){
x=++nd; ls[x]=ls[y]; rs[x]=rs[y]; sm[x]=sm[y]+;
if (L==R) return; int mid=(L+R)>>;
if (pos<=mid) ins(ls[y],ls[x],L,mid,pos); else ins(rs[y],rs[x],mid+,R,pos);
} int que(int x,int y,int L,int R,int k){
if (R==k){ return sm[y]-sm[x]; }
int mid=(L+R)>>;
if (k<=mid) return que(ls[x],ls[y],L,mid,k);
else return sm[ls[y]]-sm[ls[x]]+que(rs[x],rs[y],mid+,R,k);
}
}S; void Kruskal(){
int tot=n;
rep(i,,n) fa[i]=i;
rep(i,,m){
int u=e[i].u,v=e[i].v,x=find(u),y=find(v);
if (u==v) { ntr[i]=i; continue; }
if (x==y){
int t=T.que(u,v),k=T.v[t];
ntr[i]=k; T.cut(e[k].u,t); T.cut(e[k].v,t);
}else fa[x]=y;
tot++; T.mn[tot]=tot; T.v[tot]=i;
T.link(u,tot); T.link(v,tot);
}
rep(i,,m) S.ins(root[i-],root[i],,m,ntr[i]);
} void solve(){
rep(i,,Q){
scanf("%d%d",&l,&r);
if (op) l^=ans,r^=ans;
printf("%d\n",ans=n-S.que(root[l-],root[r],,m,l-));
}
} int main(){
freopen("bzoj3514.in","r",stdin);
freopen("bzoj3514.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&Q,&op);
T.v[]=inf; rep(i,,n) T.mn[i]=i,T.v[i]=inf;
rep(i,,m) scanf("%d%d",&e[i].u,&e[i].v);
Kruskal(); solve();
return ;
}