GERALD07加强版题解

题目描述：

　　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行每行一个整数代表该组询问的联通块个数。

题解：

　　连通问题首先考虑LCT。

　　考虑连通块个数的计算方法。

　　连通块个数=点数-去掉重边后的边数。

　　逐个枚举边，如果这条边连接的两个点没有连通，连接这条边；反之，把两点间最早的边弹出，连接这条边，并记录弹出边的编号。

　　每次查询区间时，如果这条边弹出的边在区间内，那么这条边是无效的。

　　所以问题转化为求区间内小于某个数的数的个数，可以主席树维护。

　　时间复杂度$O(nlog_n)$

Code:

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int N=;

 const int inf=1e9+;

 int n,m,k,ty,cnt,top;

 int a[N<<],st[N<<],ch[N<<][],f[N<<],rev[N<<],mi[N<<];

 int u[N],v[N],rt[N],b[N],an[N];

 struct seg{

     int lc,rc,w;

 }t[N<<];

 int read()

 {

     int s=;char c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<=''){

         s=(s<<)+(s<<)+c-'';

         c=getchar();

     }

     return s;

 }

 int get(int x)

 {

     return ch[f[x]][]==x;

 }

 bool isroot(int x)

 {

     return ch[f[x]][]!=x&&ch[f[x]][]!=x;

 }

 void pushup(int x)

 {

     mi[x]=a[x];

     if(ch[x][]) mi[x]=min(mi[x],mi[ch[x][]]);

     if(ch[x][]) mi[x]=min(mi[x],mi[ch[x][]]);

 }

 void pushdown(int x)

 {

     if(rev[x]){

         swap(ch[x][],ch[x][]);

         if(ch[x][]) rev[ch[x][]]^=;

         if(ch[x][]) rev[ch[x][]]^=;

         rev[x]=;

     }

 }

 void rotate(int x)

 {

     int y=f[x],z=f[y],k=get(x);

     if(!isroot(y)){

         if(ch[z][]==y) ch[z][]=x;

         else ch[z][]=x;

     }

     f[x]=z;f[y]=x;f[ch[x][k^]]=y;

     ch[y][k]=ch[x][k^];ch[x][k^]=y;

     pushup(y);pushup(x);

 }

 void splay(int x)

 {

     top=;st[++top]=x;

     for(int i=x;!isroot(i);i=f[i]) st[++top]=f[i];

     for(int i=top;i>=;i--) pushdown(st[i]);

     while(!isroot(x)){

         int y=f[x];

         if(!isroot(y)){

             if(get(x)==get(y)) rotate(y);

             else rotate(x);

         }

         rotate(x);

     }

 }

 void access(int x)

 {

     for(int y=;x;y=x,x=f[x]){

         splay(x);ch[x][]=y;pushup(x);

     }

 }

 void makeroot(int x)

 {

     access(x);splay(x);

     rev[x]^=;

 }

 void split(int x,int y)

 {

     makeroot(x);

     access(y);splay(y);

 }

 void link(int x,int y)

 {

     makeroot(x);

     f[x]=y;

 }

 void cut(int x,int y)

 {

     split(x,y);

     f[x]=ch[y][]=;

 }

 int find(int x)

 {

     access(x);splay(x);

     pushdown(x);

     while(ch[x][]){

         pushdown(ch[x][]);

         x=ch[x][];

     }

     splay(x);

     return x;

 }

 void insert(int lk,int &rk,int l,int r,int x)

 {

     if(rk==) rk=++cnt;

     t[rk].w=t[lk].w+;

     if(l==r) return;

     int mid=(l+r)>>;

     if(x<=mid){

         t[rk].rc=t[lk].rc;

         insert(t[lk].lc,t[rk].lc,l,mid,x);

     }

     else{

         t[rk].lc=t[lk].lc;

         insert(t[lk].rc,t[rk].rc,mid+,r,x);

     }

 }

 int que(int lk,int rk,int L,int R,int l,int r)

 {

     if(L>=l&&R<=r) return t[rk].w-t[lk].w;

     int mid=(L+R)>>;

     if(r<=mid) return que(t[lk].lc,t[rk].lc,L,mid,l,r);

     else if(l>mid) return que(t[lk].rc,t[rk].rc,mid+,R,l,r);

     else return que(t[lk].lc,t[rk].lc,L,mid,l,r)+que(t[lk].rc,t[rk].rc,mid+,R,l,r);

 }

 int main()

 {

     n=read();m=read();k=read();ty=read();

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

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

         u[i]=read();v[i]=read();a[i+n]=i;

         if(u[i]!=v[i]){

             int x=find(u[i]),y=find(v[i]);

             if(x==y){

                 split(u[i],v[i]);

                 b[i]=mi[v[i]];

                 cut(u[b[i]],b[i]+n);

                 cut(b[i]+n,v[b[i]]);

             }

             link(u[i],i+n);

             link(i+n,v[i]);

             insert(rt[i-],rt[i],,m,b[i]);

         }

         else rt[i]=rt[i-];

     }

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

         int l=read(),r=read();

         if(ty){

             l^=an[i-];r^=an[i-];

         }

         an[i]=n-que(rt[l-],rt[r],,m,,l-);

     }

     for(int i=;i<=k;i++) printf("%d\n",an[i]);

     return ;

 }

巴特西

GERALD07加强版题解

最新文章

热门文章