GERALD07加强版:lct,主席树，边化点

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

传送门。

lct这么神仙的东西一个题解都不写怎么行？？？

神仙思路啊。

其实不是很难但是的确不容易想到。

我们考虑答案是什么。

首先刚开始有n个点分别是联通块，然后你连了一些边使联通块减少了。

怎么减少的呢？就是区间的边的生成树上边的数量。因为如果不是生成树上的边，那么一定与生成树上的边成环了而不会合并联通块。

怎么判断边是不是区间内生成树上的边呢？判断依据就是它有没有和前面的边成环。

那么我们先把边连起来，当连边时我们发现这两个点已经联通时，这条边就可以取代出现的最早的那条边。

如果它取代的那条边不在区间之内，那么这条边就在生成树上。

所以就来一棵LCT，边化点后维护最大编号就行，把每条边插入之前询问会被替代的边，存在数组lst里。

那么对于每一组询问，问题就变成了问在数组lst下标[l,r]内lst值小于l的有几个。

用主席树维护一下就好了。

记住这种思路。

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int c[][],f[],w[],n,m,k,opt,fid[],lst[],q[];

 int x[],y[],ans,rt[],v[],t[][],lz[],cnt;

 int find(int p){return fid[p]==p?p:fid[p]=find(fid[p]);}

 #define lc c[p][0]

 #define rc c[p][1]

 bool not_root(int p){return c[f[p]][]==p||c[f[p]][]==p;}

 void rev(int p){lc^=rc^=lc^=rc;lz[p]^=;}

 void down(int p){if(lz[p])rev(lc),rev(rc),lz[p]=;}

 void up(int p){w[p]=min(p>n?p:,min(w[lc],w[rc]));}

 void rotate(int p){

     int fa=f[p],gr=f[fa],dir=c[fa][]==p,br=c[p][!dir];

     if(not_root(fa))c[gr][c[gr][]==fa]=p; c[p][!dir]=fa; c[fa][dir]=br;

     f[p]=gr; f[fa]=p; f[br]=fa; up(fa);

 }

 void splay(int p){

     int res=p,top=;q[++top]=p;

     while(not_root(res))q[++top]=res=f[res];

     while(top)down(q[top--]);

     while(not_root(p)){

         int fa=f[p],gr=f[fa];

         if(not_root(fa))rotate(c[fa][]==p^c[gr][]==fa?fa:p);

         rotate(p);

     }

     up(p);

 }

 void access(int p){for(int y=;p;p=f[y=p])splay(p),rc=y,up(p);}

 void make_root(int p){access(p);splay(p);rev(p);}

 void split(int x,int y){make_root(x);access(y);splay(y);}

 void cut(int x,int y){split(x,y);f[x]=c[y][]=;up(y);}

 void link(int x,int y){make_root(x);f[x]=y;up(y);}

 void build(int &p,int cpy,int adx,int l=,int r=m){

     if(!p)p=++cnt;

     if(l==r){v[p]=v[cpy]+;return;}

     if(adx<=l+r>>)build(t[p][],t[cpy][],adx,l,l+r>>),t[p][]=t[cpy][];

     else build(t[p][],t[cpy][],adx,(l+r>>)+,r),t[p][]=t[cpy][];

     v[p]=v[t[p][]]+v[t[p][]];//printf("%d %d %d\n",l,r,v[p]);

 }

 int ask(int p1,int p2,int l,int r,int cl=,int cr=m){//printf("%d %d %d %d\n",cl,cr,v[p2],v[p1]);

     if(!(v[p2]-v[p1]))return ;

     if(l<=cl&&cr<=r)return v[p2]-v[p1];

     return (l<=cl+cr>>?ask(t[p1][],t[p2][],l,r,cl,cl+cr>>):)+(r>cl+cr>>?ask(t[p1][],t[p2][],l,r,(cl+cr>>)+,cr):);

 }

 int main(){w[]=;

     scanf("%d%d%d%d",&n,&m,&k,&opt);

     for(int i=;i<=n;++i)fid[i]=i;

     for(int i=;i<=m;++i){

         scanf("%d%d",&x[i],&y[i]);

         if(x[i]==y[i])lst[i]=i;

         else if(find(x[i])!=find(y[i]))fid[fid[x[i]]]=fid[y[i]],link(x[i],n+i),link(n+i,y[i]);

         else split(x[i],y[i]),lst[i]=w[y[i]]-n,cut(lst[i]+n,x[lst[i]]),cut(lst[i]+n,y[lst[i]]),

             link(x[i],n+i),link(y[i],n+i);

         build(rt[i],rt[i-],lst[i]);//printf("%d\n",lst[i]);

     }

     for(int i=,l,r;i<=k;++i){

         scanf("%d%d",&l,&r);

         if(opt)l^=ans,r^=ans;

         ans=n-ask(rt[l-],rt[r],,l-);

         printf("%d\n",ans);

     }

 }

巴特西

GERALD07加强版:lct,主席树，边化点

最新文章

热门文章