BZOJ3514: Codechef MARCH14 GERALD07加强版(LCT，主席树)

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

解题思路：

LCT维护连通图，维护最早被删除的边。

像HH的项链那样搞就好了。

只不过是主席树。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 const int N=;

 class PST{

     #define lll tr[spc].ls

     #define rrr tr[spc].rs

     public:

         void update(int l,int r,int &spc,int lst,int pos,int v)

         {

             spc=++siz;

             tr[spc]=tr[lst];

             tr[spc].val+=v;

             if(l==r)

                 return ;

             int mid=(l+r)>>;

             if(pos<=mid)

                 update(l,mid,tr[spc].ls,tr[lst].ls,pos,v);

             else

                 update(mid+,r,tr[spc].rs,tr[lst].rs,pos,v);

             return ;

         }

         int query(int l,int r,int ll,int rr,int spc)

         {

             if(!spc)

                 return ;

             if(l>rr||ll>r)

                 return ;

             if(ll<=l&&r<=rr)

                 return tr[spc].val;

             int mid=(l+r)>>;

             return query(l,mid,ll,rr,lll)+query(mid+,r,ll,rr,rrr);

         }

         void fit(int array_size)

         {

             size=array_size;

             return ;

         }

         int Query(int l,int r)

         {

             int ans=;

             ans=query(,size,l,r,root[r]);

             return ans;

         }

         void ops(int pos)

         {

             root[pos]=root[pos-];

             return ;

         }

         void Add(int i,int pos,int v)

         {

             update(,size,root[i],root[i],pos,v);

             return ;

         }

     private:

         struct trnt{

             int ls;

             int rs;

             int val;

         }tr[N*];

         int root[N];

         int siz;

         int size;

     #undef lll

     #undef rrr

 }P;

 class LCT{

     #define lll tr[spc].ch[0]

     #define rrr tr[spc].ch[1]

     #define ls ch[0]

     #define rs ch[1]

     public:

         bool whc(int spc)

         {

             return tr[tr[spc].fa].rs==spc;

         }

         void pushup(int spc)

         {

             tr[spc].mv=tr[spc].sl;

             if(lll)

                 tr[spc].mv=std::min(tr[spc].mv,tr[lll].mv);

             if(rrr)

                 tr[spc].mv=std::min(tr[spc].mv,tr[rrr].mv);

             return ;

         }

         void trr(int spc)

         {

             if(!spc)

                 return ;

             std::swap(lll,rrr);

             tr[spc].lzt^=;

             return ;

         }

         void pushdown(int spc)

         {

             if(tr[spc].lzt)

             {

                 trr(lll);

                 trr(rrr);

                 tr[spc].lzt=;

             }

             return ;

         }

         void recal(int spc)

         {

             if(!tr[spc].anc)

                 recal(tr[spc].fa);

             pushdown(spc);

             return ;

         }

         void rotate(int spc)

         {

             int f=tr[spc].fa;

             bool k=whc(spc);

             tr[f].ch[k]=tr[spc].ch[!k];

             tr[spc].ch[!k]=f;

             if(tr[f].anc)

             {

                 tr[f].anc=;

                 tr[spc].anc=;

             }else

                 tr[tr[f].fa].ch[whc(f)]=spc;

             tr[spc].fa=tr[f].fa;

             tr[f].fa=spc;

             tr[tr[f].ch[k]].fa=f;

             pushup(f);

             pushup(spc);

             return ;

         }

         void splay(int spc)

         {

             recal(spc);

             while(!tr[spc].anc)

             {

                 int f=tr[spc].fa;

                 if(tr[f].anc)

                 {

                     rotate(spc);

                     return ;

                 }

                 if(whc(spc)^whc(f))

                     rotate(spc);

                 else

                     rotate(f);

                 rotate(spc);

             }

             return ;

         }

         void access(int spc)

         {

             int lst=;

             while(spc)

             {

                 splay(spc);

                 tr[rrr].anc=;

                 tr[lst].anc=;

                 rrr=lst;

                 pushup(spc);

                 lst=spc;

                 spc=tr[spc].fa;

             }

             return ;

         }

         void Mtr(int spc)

         {

             access(spc);

             splay(spc);

             trr(spc);

             return ;

         }

         void split(int x,int y)

         {

             Mtr(x);

             access(y);

             splay(y);

             return ;

         }

         void link(int x,int y)

         {

             Mtr(x);

             tr[x].fa=y;

             return ;

         }

         bool check(int x,int y)

         {

             Mtr(x);

             access(y);

             splay(y);

             pushdown(y);

             while(tr[y].ls)

             {

                 y=tr[y].ls;

                 pushdown(y);

             }

             return x==y;

         }

         int minplace(int x,int y)

         {

             split(x,y);

             return tr[y].mv;

         }

         void cut(int x,int y)

         {

             split(x,y);

             tr[y].ls=;

             tr[x].fa=;

             tr[x].anc=true;

             pushup(y);

             return ;

         }

         void fit(int size1,int size2)

         {

             siz=size1+size2;

             for(int i=;i<=size1;i++)

                 tr[i].sl=0x3f3f3f3f;

             for(int i=;i<=size2;i++)

                 tr[i+size1].sl=i;

             for(int i=;i<=siz;i++)

             {

                 tr[i].anc=true;

                 pushup(i);

             }

             return ;

         }

     private:

         struct int_2{

             int v;

             int p;

         };

         struct trnt{

             int ch[];

             int fa;

             int lzt;

             bool anc;

             int sl;

             int mv;

         }tr[N];

         int siz;

     #undef lll

     #undef rrr

     #undef ls

     #undef rs

 }T;

 int n,m,k,t;

 int lastans;

 int from[N];

 int plc[N];

 int to[N];

 int no[N];

 int main()

 {

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

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

     {

         scanf("%d%d",&from[i],&to[i]);

         no[i]=i;

         plc[i]=n+i;

     }

     T.fit(n,m);

     P.fit(m);

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

     {

         P.ops(i);

         int a=from[i],b=to[i];

         if(a==b)

             continue;

         if(T.check(a,b))

         {

             int pos=T.minplace(a,b);

             P.Add(i,pos,-);

             T.cut(plc[pos],from[pos]);

             T.cut(plc[pos],to[pos]);

         }

         T.link(plc[i],a);

         T.link(plc[i],b);

         P.Add(i,i,);

     }

     while(k--)

     {

         int l,r;

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

         if(t)

         {

             l^=lastans;

             r^=lastans;

         }

         lastans=n-P.Query(l,r);

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

     }

     return ;

 }

巴特西