题目大意

　　有\(n\)个节点，标号从1到\(n\)，这\(n\)个节点一开始相互不连通。第\(i\)个节点的初始权值为\(a_i\)，接下来有如下一些操作：

　　\(U~x~y\)：加一条边，连接第\(x\)个节点和第\(y\)个节点。

　　\(A1~x~v\)：将第\(x\)个节点的权值增加\(v\)。

　　\(A2~x~v\)：将第\(x\)个节点所在的连通块的所有节点的权值都增加\(v\)。

　　\(A3~v\)：将所有节点的权值都增加\(v\)。

　　\(F1~x\)：输出第\(x\)个节点当前的权值。

　　\(F2~x\)：输出第\(x\)个节点所在的连通块中，权值最大的节点的权值。

　　\(F3\)：输出所有节点中，权值最大的节点的权值。

　　\(n,m\leq 300000,-1000\leq v,a_i\leq 1000\)

题解

　　如果没有点修改就可以用可合并堆维护。但是现在有点修改，这样就需要遍历\(x\)到根。然而可合并堆的深度是\(O(n)\)的，这样做会直接TLE。

　　那么还有没有什么其他的数据结构能支持合并和修改权值呢？

　　答案是：有。可以用线段树或非旋treap。合并均摊是\(O(\log n)\)的。我选择了treap。

　　treap合并在我的博客的另外一篇里面有写。

　　再拿一棵树维护所有treap的最大值的最大值。

　　用一个数维护全部节点的权值同时加了多少。输出时把这个加到答案上面去就可以了。

　　时间复杂度：\(O((n+m)\log n)\)

　　UPD：直接用treap的merge就行了。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
             
               pii;typedef pair
              
                pll;void sort(int &a,int &b){ if(a>b) swap(a,b);}void open(const char *s){#ifndef ONLINE_JUDGE char str[100]; sprintf(str,"%s.in",s); freopen(str,"r",stdin); sprintf(str,"%s.out",s); freopen(str,"w",stdout);#endif}struct node{ int f,ls,rs; int k,v,t,s; int sz; int u;};node a[300010];int cnt=0;int newnode(int u,int v){ int x=++cnt; a[x].u=u; a[x].v=a[x].s=v; a[x].sz=1; return x;}void add(int x,int v){ a[x].v+=v; a[x].s+=v; a[x].t+=v;}void push(int x){ if(a[x].t) { if(a[x].ls) add(a[x].ls,a[x].t); if(a[x].rs) add(a[x].rs,a[x].t); a[x].t=0; }}void mt(int x){ a[x].s=a[x].v; if(a[x].ls) a[x].s=max(a[x].s,a[a[x].ls].s); if(a[x].rs) a[x].s=max(a[x].s,a[a[x].rs].s); a[x].sz=a[a[x].ls].sz+a[a[x].rs].sz+1;}void pushdown(int x){ if(a[x].f) pushdown(a[x].f); push(x);}void pushup(int x){ mt(x); if(a[x].f) pushup(a[x].f);}int merge(int x,int y){ if(!x||!y) return x+y; if(a[x].k
               
                a[y].k) swap(x,y); push(x); pii s=split(y,a[x].v); a[x].ls=merge(a[x].ls,s.first); a[x].rs=merge(a[x].rs,s.second); if(a[x].ls) a[a[x].ls].f=x; if(a[x].rs) a[a[x].rs].f=x; mt(x); return x;}int f[300010];int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}int rt[300010];multiset
                
                  s;int main(){ open("bzoj2333"); int n; scanf("%d",&n); int i,x; for(i=1;i<=n;i++) { scanf("%d",&x); rt[i]=newnode(i,x); f[i]=i; s.insert(x); } char op[5]; int y,v; int all=0; int m; int ans; scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%s",op); if(op[0]=='U') { scanf("%d%d",&x,&y); x=find(x); y=find(y); if(x==y) continue; f[x]=y; s.erase(s.find(min(a[rt[x]].s,a[rt[y]].s))); rt[y]=join(rt[x],rt[y]); } else if(op[0]=='A'&&op[1]=='1') { scanf("%d%d",&x,&v); y=find(x); s.erase(s.find(a[rt[y]].s)); pushdown(x); a[x].v+=v; pushup(x); s.insert(a[rt[y]].s); } else if(op[0]=='A'&&op[1]=='2') { scanf("%d%d",&x,&v); x=find(x); s.erase(s.find(a[rt[x]].s)); add(rt[x],v); s.insert(a[rt[x]].s); } else if(op[0]=='A'&&op[1]=='3') { scanf("%d",&y); all+=y; } else if(op[1]=='1') { scanf("%d",&x); pushdown(x); ans=a[x].v+all; printf("%d\n",ans); } else if(op[1]=='2') { scanf("%d",&x); x=find(x); ans=a[rt[x]].s+all; printf("%d\n",ans); } else { ans=*s.rbegin()+all; printf("%d\n",ans); } } return 0;}