有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，代表节点个数。

接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。

再下一行输入一个整数Q，代表接下来的操作数。

最后输入Q行，每行的格式如题目描述所示。

对于操作F1, F2, F3，输出对应的结果，每个结果占一行。

 对于30%的数据，保证 N<=100，Q<=10000

对于80%的数据，保证 N<=100000，Q<=100000

对于100%的数据，保证 N<=300000，Q<=300000

对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000

Day2

#include<cstdio>#include<iostream>#define lc k<<1#define rc k<<1|1using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;} const int N=3e5+5;const int M=N<<2;int n,m,cnt,a[N],dfn[N],w[N];int fa[N],ed[N],next[N];int mx[M],de[M];struct unline{int x,y,op;}q[N];inline void update(int k){    mx[k]=max(mx[lc],mx[rc]);}inline void pushdown(int k){    if(!de[k]) return ;    mx[lc]+=de[k];    mx[rc]+=de[k];    de[lc]+=de[k];    de[rc]+=de[k];    de[k]=0;}void build(int k,int l,int r){    if(l==r){mx[k]=dfn[l];return ;}    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    update(k);}void change(int k,int l,int r,int x,int y,int v){    if(l==x&&r==y){        mx[k]+=v;        de[k]+=v;        return ;    }    pushdown(k);    int mid=l+r>>1;    if(y<=mid) change(lc,l,mid,x,y,v);    else if(x>mid) change(rc,mid+1,r,x,y,v);    else change(lc,l,mid,x,mid,v),change(rc,mid+1,r,mid+1,y,v);    update(k);}int query(int k,int l,int r,int x,int y){    if(l==x&&r==y) return mx[k];    pushdown(k);    int mid=l+r>>1;    if(y<=mid) return query(lc,l,mid,x,y);    else if(x>mid) return query(rc,mid+1,r,x,y);    else return max(query(lc,l,mid,x,mid),query(rc,mid+1,r,mid+1,y));    update(k);}int find(int x){    return fa[x]==x?x:fa[x]=find(fa[x]);}inline void merge(int i){    int r1,r2;    r1=find(q[i].x);r2=find(q[i].y);    if(r1!=r2){        fa[r2]=r1;next[ed[r1]]=r2;ed[r1]=ed[r2];    }}int main(){    n=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=n;i++) fa[i]=ed[i]=i;    m=read();char s[10];    for(int i=1;i<=m;i++){        scanf("%s",s);        if(s[0]==‘U‘){            q[i].op=1;            q[i].x=read();q[i].y=read();            merge(i);        }        if(s[0]==‘A‘){            q[i].op=s[1]-‘0‘+1;            q[i].x=read();            if(s[1]!=‘3‘) q[i].y=read();        }        if(s[0]==‘F‘){            q[i].op=s[1]-‘0‘+4;            if(s[1]!=‘3‘) q[i].x=read();        }    }    for(int i=1;i<=n;i++){        if(fa[i]==i){            for(int j=i;j;j=next[j]){                w[j]=++cnt;dfn[cnt]=a[j];            }        }    }    build(1,1,n);    for(int i=1;i<=n;i++) fa[i]=ed[i]=i;    for(int i=1,r;i<=m;i++){        if(q[i].op==1) {merge(i);continue;}        if(q[i].op==2) change(1,1,n,w[q[i].x],w[q[i].x],q[i].y);        if(q[i].op==3) r=find(q[i].x),change(1,1,n,w[r],w[ed[r]],q[i].y);        if(q[i].op==4) change(1,1,n,1,n,q[i].x);        if(q[i].op==5) printf("%d\n",query(1,1,n,w[q[i].x],w[q[i].x]));        if(q[i].op==6) r=find(q[i].x),printf("%d\n",query(1,1,n,w[r],w[ed[r]]));        if(q[i].op==7) printf("%d\n",query(1,1,n,1,n));    }    return 0;}