BZOJ3514. Codechef MARCH14 GERALD07
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 2
Sample Output:
2
1
3
1
Hint:
对于(100)%的数据，(1≤N、M、K≤200,000)。
题目分析：
首先询问是在线的，因此我们需要一个数据结构动态维护图的连通性，很容易想到使用(LCT)维护当前森林的边数(sum[i])，但是(LCT)维护森林之后如何判断一段区间内的边的使用情况呢？我们可以每次(LCT)需要删边时删去编号最小的边，并用主席树来删去的边的编号在某个区间的个数。那么我们使用([L,R])这一区间的边时，为了保证连通图是一棵森林，会把一些编号在([1,L-1])的边删去，这时，我们再把([1,L-1])这些边的贡献再加回来，那么答案就是(sum[R]-sum[L-1])(+)([)在加入编号为([L,R])的边时删去的编号范围在([1,L-1])的边的数目(])。
代码如下(马蜂很丑，不喜勿喷)——
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Tp template<typename T>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define maxn 400005
#define inf 100000000
using namespace std;
int n,m,q,T,ans,tot,summ[maxn],rt[maxn],tag[maxn],st[maxn],s[maxn],f[maxn],son[maxn][2],v[maxn],minn[maxn],sum[maxn*20],trl[maxn*20],trr[maxn*20],uu[maxn],vv[maxn];
inline void rev(int x){tag[x]^=1,swap(son[x][1],son[x][0]);}
inline bool nroot(int x){return son[f[x]][0]==x||son[f[x]][1]==x;}
inline bool get(int x){return son[f[x]][1]==x;}
inline void pushup(int x){
if(v[minn[son[x][0]]]<v[minn[son[x][1]]]) minn[x]=minn[son[x][0]];
else minn[x]=minn[son[x][1]];if(v[minn[x]]>v[x]) minn[x]=x;s[x]=s[son[x][0]]+s[son[x][1]]+1;
}
inline void pushdown(int x){if(!tag[x]) return;if(son[x][0]) rev(son[x][0]);if(son[x][1]) rev(son[x][1]);tag[x]=0;}
inline void rotate(int x){
int fa=f[x],ff=f[fa],which=get(x);if(nroot(fa)) son[ff][son[ff][1]==fa]=x;son[fa][which]=son[x][which^1],son[x][which^1]=fa;
f[son[fa][which]]=fa,f[fa]=x,f[x]=ff;pushup(fa),pushup(x);
}
inline void splay(int x){
int y=x,top=0;st[++top]=x;while(nroot(y)) y=f[y],st[++top]=y;
while(top) pushdown(st[top--]);while(nroot(x)){y=f[x];if(nroot(y)) rotate(get(x)==get(y)?y:x);rotate(x);}
}
inline void access(int x){for(register int y=0;x;x=f[y=x]) splay(x),son[x][1]=y,pushup(x);}
inline void makeroot(int x){access(x),splay(x),rev(x);}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline int findroot(int x){access(x),splay(x);while(son[x][0]) pushdown(x),x=son[x][0];splay(x);return x;}
inline void link(int x,int y){makeroot(x);if(findroot(y)!=x) f[x]=y;}
inline void cut(int x,int y){makeroot(x);if(findroot(y)==x&&s[x]==2) son[x][1]=f[y]=0,pushup(x);}
inline void modify(int &now,int lst,int l,int r,int x){
now=++tot;sum[now]=sum[lst]+1;if(l==r) return;int mid=l+r>>1;
if(mid>=x) modify(trl[now],trl[lst],l,mid,x),trr[now]=trr[lst];
else modify(trr[now],trr[lst],mid+1,r,x),trl[now]=trl[lst];
}
inline int query(int now,int l,int r,int ll,int rr){
if(ll>rr) return 0;if(l>=ll&&r<=rr) return sum[now];int mid=l+r>>1,res=0;
if(mid>=ll) res=query(trl[now],l,mid,ll,rr);if(mid<rr) res+=query(trr[now],mid+1,r,ll,rr);return res;
}
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[25];
public:
FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x,const char& ch)
{
if (x<0) pc('-'),x=-x; RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
int main(){
F.read(n),F.read(m),F.read(q),F.read(T);for(register int i=0;i<=n;i++) s[i]=1,minn[i]=i,v[i]=inf;s[0]=0;
for(register int i=1,x,y;i<=m;i++){
summ[i]=summ[i-1]+1;F.read(uu[i]),F.read(vv[i]);x=uu[i],y=vv[i];if(x==y){summ[i]--,rt[i]=rt[i-1];continue;}if(findroot(x)==findroot(y))
{summ[i]--,split(x,y);int num=v[minn[y]],l=uu[num],r=vv[num];modify(rt[i],rt[i-1],1,m,num),cut(num+n,l),cut(num+n,r);}
else rt[i]=rt[i-1];minn[i+n]=i+n,v[i+n]=i,s[i+n]=1,link(x,i+n),link(i+n,y);
}
for(register int i=1,x,y;i<=q;i++){
F.read(x),F.read(y);if(T==1) x^=ans,y^=ans;
ans=summ[y]-summ[x-1]+query(rt[y],1,m,1,x-1)-query(rt[x-1],1,m,1,x-1);ans=n-ans;F.write(ans,'
');
}
return F.flush(),0;
}