可以大力写一个平衡树启发式合并,除了每个连通块维护一个平衡树再对全局维护一个平衡树,每个节点表示某一个连通块的最大值.我的常数比较大,危险地卡过去了.
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int maxn=300005; struct node{ node *ch[2];int Max,mark,ord,num,key,sz; node(int x,int w){ ord=rand();num=x;Max=key=w;mark=0; ch[0]=ch[1]=0;sz=1; } void update(){ Max=key;sz=1; if(ch[0])sz+=ch[0]->sz; if(ch[1])sz+=ch[1]->sz; if(ch[0]&&ch[0]->Max>Max)Max=ch[0]->Max; if(ch[1]&&ch[1]->Max>Max)Max=ch[1]->Max; } void add(int x){ Max+=x;mark+=x;key+=x; } void pushdown(){ if(mark){ if(ch[0])ch[0]->add(mark); if(ch[1])ch[1]->add(mark); mark=0; } } }; node* Super; void rot(node* &rt,int t){ node* c=rt->ch[t];rt->pushdown();c->pushdown(); rt->ch[t]=c->ch[t^1];c->ch[t^1]=rt;rt=c; c->ch[t^1]->update();c->update(); } void Insert(node* &rt,int x,int w){//printf("%d %d ",x,w); if(!rt){ rt=new node(x,w);return; } int t=(x>rt->num); rt->pushdown(); Insert(rt->ch[t],x,w); rt->update(); if(rt->ch[t]->ord>rt->ord)rot(rt,t); } void remove(node* &rt,int x){ if(rt->num!=x){ rt->pushdown(); remove(rt->ch[x>rt->num],x);rt->update(); }else{ if(!rt->ch[0]){ rt=rt->ch[1]; }else if(!rt->ch[1]){ rt=rt->ch[0]; }else if(rt->ch[0]->ord>rt->ch[1]->ord){ rot(rt,0);remove(rt->ch[1],x);rt->update(); }else{ rot(rt,1);remove(rt->ch[0],x);rt->update(); } } } int ufs[maxn]; int find(int x){ return (x==ufs[x])?x:ufs[x]=find(ufs[x]); } node* root[maxn]; void Union(node* rt1,node* &rt2){ if(!rt1)return; Insert(rt2,rt1->num,rt1->key);rt1->pushdown(); Union(rt1->ch[0],rt2);Union(rt1->ch[1],rt2); delete rt1; } void link(int a,int b){ int ra=find(a),rb=find(b); if(root[ra]->sz>root[rb]->sz)swap(ra,rb); ufs[ra]=rb; Union(root[ra],root[rb]); remove(Super,ra);remove(Super,rb);Insert(Super,find(a),root[find(a)]->Max); } void incr(node* rt,int x,int w){ rt->pushdown(); if(x==rt->num){ rt->key+=w;rt->update();return; }else{ incr(rt->ch[x>rt->num],x,w);rt->update();return; } } int getkey(node* rt,int x){ rt->pushdown(); if(rt->num==x)return rt->key; return getkey(rt->ch[x>rt->num],x); } int Globalmark=0; int main(){ int n;scanf("%d",&n); int x; for(int i=1;i<=n;++i){ scanf("%d",&x); Insert(Super,i,x); root[i]=new node(i,x); ufs[i]=i; } char buf[5]; int m;scanf("%d",&m); int a,b; for(int i=1;i<=m;++i){ scanf("%s",buf); if(buf[0]=='U'){ scanf("%d%d",&a,&b); if(find(a)!=find(b))link(a,b); } else if(buf[0]=='A'){ if(buf[1]=='1'){ scanf("%d%d",&a,&b); incr(root[find(a)],a,b);remove(Super,find(a));Insert(Super,find(a),root[find(a)]->Max); }else if(buf[1]=='2'){ scanf("%d%d",&a,&b); root[find(a)]->add(b);incr(Super,find(a),b); }else{ scanf("%d",&b);Globalmark+=b; } }else if(buf[0]=='F'){ if(buf[1]=='1'){ scanf("%d",&a);printf("%d ",getkey(root[find(a)],a)+Globalmark); }else if(buf[1]=='2'){ scanf("%d",&a);printf("%d ",root[find(a)]->Max+Globalmark); }else{ printf("%d ",Super->Max+Globalmark); } } } return 0; }