题目

 

 

分析

　　看起来就是一个支持link的东西。

　　但有环，考虑缩点......

　　但疯狂Tle。大概是常数卡不过去。

　　行走的大常数noble_

 

代码

#include 
      
       #define lc son[x][0]#define rc son[x][1]using namespace std;const int maxn=150005;int son[maxn][2],s[maxn],v[maxn],lazy[maxn],fa[maxn],st[maxn],dig[100];int pa[maxn], belong[maxn], a[maxn];inline int findset(int x){
    if(belong[x]==x) return x;else return belong[x]=findset(belong[x]);}inline int find(int x){
    if(pa[x]==x) return x;else return pa[x]=find(pa[x]);}inline int ws(int x){
    return son[findset(fa[x])][1]==x;}inline int isroot(int x){
    int f=findset(fa[x]);return !(son[f][0]==x||son[f][1]==x);}inline int rev(int x){lazy[x]^=1; swap(lc,rc);}inline void pushdown(int x){    if(!lazy[x]) return;    if(lc) rev(lc); if(rc) rev(rc); lazy[x]=0;}inline void update(int x){ s[x]=s[lc]+s[rc]+v[x]; }inline void rot(int x){    int f=fa[x], ff=fa[f],w1=ws(x),w2=ws(fa[x]),xx=son[x][!w1];    if(!isroot(f))son[ff][w2]=x;son[x][!w1]=f;son[f][w1]=xx;    if(xx)fa[xx]=f;fa[f]=x;fa[x]=ff;    update(f);update(x);}inline void splay(int x){    int y=x,z=0; st[++z]=y; pushdown(x);    while(!isroot(y)) st[++z]=y=findset(fa[y]);    while(z) pushdown(st[z--]),fa[st[z]]=findset(fa[st[z]]);    for(;!isroot(x);rot(x))        if(ws(x)==ws(fa[x])&&!isroot(fa[x])) rot(fa[x]);    update(x); }inline void access(int x){    for(int y=0;x;x=findset(fa[y=x])){        splay(x); rc=y; if(y) fa[y]=x; update(x);    }}inline void makeroot(int x){    access(x); splay(x); rev(x);}inline int findroot(int x){    access(x); splay(x);    while(lc) pushdown(x),x=lc;    return x;}inline void link(int x,int y){    makeroot(x);    if(findroot(y)==x) return;    fa[x]=y;}inline void merge(int x,int y){    if(!x) return;    belong[findset(x)]=findset(y); pushdown(x);    if(x!=y) v[y]+=v[x];    if(lc) merge(lc,y); if(rc) merge(rc,y);//    puts("**********************");    lc=rc=0;}inline int in(){      char c=getchar();      for (;c>'9'||c<'0';c=getchar());      int num=0;      for (;c>='0'&&c<='9';c=getchar())         num=num*10+c-'0';      return num;  } inline void write(int x){    if (!x)    {        putchar('0');        putchar('\n');        return;    }    dig[0]=0;    while (x)    {        dig[++dig[0]]=x%10;        x/=10;    }    for (int i=dig[0];i>=1;--i) putchar(dig[i]+'0');    putchar('\n');}int main(){    int n,m; n=in();m=in();    for(register int i= 1;i<=n;++i) v[i]=in(),pa[i]=belong[i]=i,a[i]=v[i];    int p,x,y;    while(m--){        p=in();x=in();y=in();        if(p==1){            x=findset(x);y=findset(y);            if(x==y) continue;            int r1=find(x), r2=find(y);            if(r1!=r2){                pa[r2]=r1;                link(x,y);            }            else{                makeroot(x); access(y); splay(y);                merge(y,y); update(y);            }        }        if(p==2){            int xx=x;            x=findset(x);            access(x); splay(x); v[x]+=y-a[xx]; a[xx]=y;             update(x);        }        if(p==3){            x=findset(x); y=findset(y);            if(find(x)!=find(y) ){                write(-1); continue;            }            makeroot(x); access(y); splay(y);            write(s[y]);        }    }    return 0;}