UVALive - 5031 Graph and Queries (并查集+平衡树/线段树)

给定一个图，支持三种操作:

1.删除一条边

2.查询与x结点相连的第k大的结点

3.修改x结点的权值

解法：离线倒序操作，平衡树or线段树维护连通块中的所有结点信息，加个合并操作就行了。

感觉线段树要好写很多。

平衡树(Treap)版:

 #include<bits/stdc++.h>
 typedef long long ll;
 using namespace std;
 const int N=5e5+;
 struct E {
     int u,v;
 } e[N];
 int a[N],faz[N],n,m,del[N];
 int father(int x) {return ~faz[x]?faz[x]=father(faz[x]):x;}

 struct Treap {
     static const int N=1e6+;
     int rnd() {static int seed=time()%0x7fffffff; return seed=seed*48271ll%0x7fffffff;}
     int ch[N][],siz[N],val[N],fa[N],tot,rd[N],rt[N];
     void init() {tot=ch[][]=ch[][]=siz[]=val[]=rd[]=;}
     int newnode(int x) {
         int u=++tot;
         ch[u][]=ch[u][]=;
         siz[u]=,val[u]=x,rd[u]=rnd();
         return u;
     }
     void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}
     void rot(int& u,int f) {
         int v=ch[u][f];
         ch[u][f]=ch[v][f^],ch[v][f^]=u;
         pu(u),pu(v),u=v;
     }
     void ins(int& u,int x) {
         if(!u) {u=newnode(x); return;}
         int f=x>=val[u];
         ins(ch[u][f],x);
         if(rd[ch[u][f]]>rd[u])rot(u,f);
         if(u)pu(u);
     }
     void del(int& u,int x) {
         if(val[u]==x) {
             if(!ch[u][])u=ch[u][];
             else if(!ch[u][])u=ch[u][];
             else {
                 int f=rd[ch[u][]]>rd[ch[u][]];
                 rot(u,f),del(ch[u][f^],x);
             }
         } else del(ch[u][x>=val[u]],x);
         if(u)pu(u);
     }
     int kth(int u,int k) {
         if(!u)return ;
         int t=siz[ch[u][]]+;
         if(k==t)return val[u];
         return k<t?kth(ch[u][],k):kth(ch[u][],k-t);
     }
     void merge(int& u,int& v) {
         if(!u)return;
         ins(v,val[u]);
         merge(ch[u][],v),merge(ch[u][],v);
     }
 } treap;

 struct Q {
     int f,u,k;
 } qr[N];
 int nqr;

 void mg(int x,int y) {
     int fx=father(x),fy=father(y);
     if(fx==fy)return;
     if(treap.siz[treap.rt[fx]]>treap.siz[treap.rt[fy]])swap(fx,fy);
     treap.merge(treap.rt[fx],treap.rt[fy]);
     faz[fx]=fy;
 }

 int main() {
     int kase=;
     while(scanf("%d%d",&n,&m)&&n) {
         treap.init();
         nqr=;
         memset(faz,-,sizeof faz);
         for(int i=; i<=n; ++i)scanf("%d",&a[i]);
         for(int i=; i<=m; ++i)scanf("%d%d",&e[i].u,&e[i].v);
         char ch;
         while(scanf(" %c",&ch)&&ch!='E') {
             if(ch=='Q')scanf("%d%d",&qr[nqr].u,&qr[nqr].k),qr[nqr++].f=;
             else if(ch=='D')scanf("%d",&qr[nqr].u),qr[nqr++].f=;
             else if(ch=='C')scanf("%d%d",&qr[nqr].u,&qr[nqr].k),swap(a[qr[nqr].u],qr[nqr].k),qr[nqr++].f=;
         }
         for(int i=; i<=n; ++i)treap.rt[i]=treap.newnode(a[i]);
         memset(del,,sizeof del);
         for(int i=; i<nqr; ++i)if(qr[i].f==)del[qr[i].u]=;
         for(int i=; i<=m; ++i)if(!del[i])mg(e[i].u,e[i].v);
         reverse(qr,qr+nqr);
         double ans=;
         int cnt=;
         for(int i=; i<nqr; ++i) {
             if(qr[i].f==) {
                 int u=qr[i].u,r=treap.rt[father(u)],k=qr[i].k;
                 ans+=treap.kth(r,treap.siz[r]-k+),cnt++;
             } else if(qr[i].f==)mg(e[qr[i].u].u,e[qr[i].u].v);
             else {
                 int u=qr[i].u,k=qr[i].k;
                 int fu=father(u);
                 treap.del(treap.rt[fu],a[u]);
                 treap.ins(treap.rt[fu],k);
                 a[u]=k;
             }
         }
         printf("Case %d: %f\n",++kase,ans/cnt);
     }
     return ;
 }

线段树版:

 #include<bits/stdc++.h>
 typedef long long ll;
 using namespace std;
 const int N=5e5+;
 struct E {
     int u,v;
 } e[N];
 int a[N],faz[N],n,m,del[N];
 int father(int x) {return ~faz[x]?faz[x]=father(faz[x]):x;}

 struct Segtree {
     static const int N=4e6+;
     int ls[N],rs[N],siz[N],tot,rt[N];
     void init() {tot=ls[]=rs[]=siz[]=;}
     int newnode() {int u=++tot; ls[u]=rs[u]=siz[u]=; return u;}
     void pu(int u) {siz[u]=siz[ls[u]]+siz[rs[u]];}
     void add(int& u,int x,int f,int l=-,int r=) {
         if(!u)u=newnode();
         siz[u]+=f;
         if(l==r)return;
         int mid=(l+r)>>;
         x<=mid?add(ls[u],x,f,l,mid):add(rs[u],x,f,mid+,r);
     }
     void merge(int& u,int v,int l=-,int r=) {
         if(!v)return;
         if(!u) {u=v; return;}
         if(l==r) {siz[u]+=siz[v]; return;}
         int mid=(l+r)>>;
         merge(ls[u],ls[v],l,mid);
         merge(rs[u],rs[v],mid+,r);
         pu(u);
     }
     int kth(int u,int k,int l=-,int r=) {
         if(l==r)return l;
         int mid=(l+r)>>;
         return k<=siz[ls[u]]?kth(ls[u],k,l,mid):kth(rs[u],k-siz[ls[u]],mid+,r);
     }
 } segtree;

 struct Q {
     int f,u,k;
 } qr[N];
 int nqr;

 void mg(int x,int y) {
     int fx=father(x),fy=father(y);
     if(fx==fy)return;
     segtree.merge(segtree.rt[fy],segtree.rt[fx]);
     faz[fx]=fy;
 }

 int main() {
     int kase=;
     while(scanf("%d%d",&n,&m)&&n) {
         segtree.init();
         nqr=;
         memset(faz,-,sizeof faz);
         for(int i=; i<=n; ++i)scanf("%d",&a[i]);
         for(int i=; i<=m; ++i)scanf("%d%d",&e[i].u,&e[i].v);
         char ch;
         while(scanf(" %c",&ch)&&ch!='E') {
             if(ch=='Q')scanf("%d%d",&qr[nqr].u,&qr[nqr].k),qr[nqr++].f=;
             else if(ch=='D')scanf("%d",&qr[nqr].u),qr[nqr++].f=;
             else if(ch=='C')scanf("%d%d",&qr[nqr].u,&qr[nqr].k),swap(a[qr[nqr].u],qr[nqr].k),qr[nqr++].f=;
         }
         for(int i=; i<=n; ++i)segtree.rt[i]=segtree.newnode(),segtree.add(segtree.rt[i],a[i],);
         memset(del,,sizeof del);
         for(int i=; i<nqr; ++i)if(qr[i].f==)del[qr[i].u]=;
         for(int i=; i<=m; ++i)if(!del[i])mg(e[i].u,e[i].v);
         reverse(qr,qr+nqr);
         double ans=;
         int cnt=;
         for(int i=; i<nqr; ++i) {
             if(qr[i].f==) {
                 int u=qr[i].u,r=segtree.rt[father(u)],k=qr[i].k;
                 if(k>&&k<=segtree.siz[r])ans+=segtree.kth(r,segtree.siz[r]-k+);
                 cnt++;
             } else if(qr[i].f==)mg(e[qr[i].u].u,e[qr[i].u].v);
             else {
                 int u=qr[i].u,k=qr[i].k;
                 int fu=father(u);
                 segtree.add(segtree.rt[fu],a[u],-);
                 segtree.add(segtree.rt[fu],k,);
                 a[u]=k;
             }
         }
         printf("Case %d: %f\n",++kase,ans/cnt);
     }
     return ;
 }