伪老年选手临时抱佛脚之LCT
正确率还挺高?只有两个小bug
然而不是说好caioj复习模板吗
啊？能升rank还能复习当然更好啦
#include#include #include #include #include #include using namespace std;struct LCT{ int f,son[2];bool fz; int d,c; LCT(){f=0;son[0]=son[1]=0;fz=false;}}tr[31000];void update(int x){ int lc=tr[x].son[0],rc=tr[x].son[1]; tr[x].c=tr[lc].c+tr[rc].c+tr[x].d;}void reverse(int x){ tr[x].fz=false; swap(tr[x].son[0],tr[x].son[1]); int lc=tr[x].son[0],rc=tr[x].son[1]; if(lc!=0)tr[lc].fz=1-tr[lc].fz; if(rc!=0)tr[rc].fz=1-tr[rc].fz;}void rotate(int x,int w){ int f=tr[x].f,ff=tr[f].f; int R,r; R=f;r=tr[x].son[w]; tr[R].son[1-w]=r; if(r!=0)tr[r].f=R; R=ff;r=x; if(tr[R].son[0]==f)tr[R].son[0]=r; else if(tr[R].son[1]==f)tr[R].son[1]=r; tr[r].f=R; R=x;r=f; tr[R].son[w]=r; tr[r].f=R; update(f); update(x);}bool isroot(int x,int rt){ int f=tr[x].f; if(f==rt||(tr[f].son[0]!=x&&tr[f].son[1]!=x))return true; else return false;}int ts,tmp[31000];void splay(int x,int rt){ ts=0;int i=x; while(isroot(i,rt)==false) { tmp[++ts]=i; i=tr[i].f; } tmp[++ts]=i; while(ts>0) { i=tmp[ts--]; if(tr[i].fz==true)reverse(i); } //~~~~reverse while(isroot(x,rt)==false) { int f=tr[x].f,ff=tr[f].f; if(isroot(f,rt)==true) { if(tr[f].son[0]==x)rotate(x,1); else rotate(x,0); } else { if(tr[ff].son[0]==f&&tr[f].son[0]==x){rotate(f,1);rotate(x,1);} else if(tr[ff].son[1]==f&&tr[f].son[1]==x){rotate(f,0);rotate(x,0);} else if(tr[ff].son[0]==f&&tr[f].son[1]==x){rotate(x,0);rotate(x,1);} else if(tr[ff].son[1]==f&&tr[f].son[0]==x){rotate(x,1);rotate(x,0);} } }}//~~~splayvoid access(int x){ int y=0; while(x!=0) { splay(x,0); tr[x].son[1]=y; if(y!=0)tr[y].f=x; update(x); y=x;x=tr[x].f; }}int makeroot(int x){ access(x);splay(x,0); tr[x].fz=1-tr[x].fz;}//-------------in---------------------void Link(int x,int y){ makeroot(x);tr[x].f=y;access(x);}int findroot(int x){ access(x);splay(x,0); while(tr[x].son[0]!=0)x=tr[x].son[0]; return x;}void change(int x,int d){ makeroot(x);access(x); tr[x].d=d;tr[x].c=d;}int getsum(int x,int y){ makeroot(x); access(y);splay(y,0); return tr[y].c;}//------------out---------------------char ss[20];int main(){ freopen("data.in","r",stdin); freopen("1.out","w",stdout); int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&tr[i].d), tr[i].c=tr[i].d; int Q,x,y,k; scanf("%d",&Q); while(Q--) { scanf("%s",ss+1); if(ss[1]=='b') { scanf("%d%d",&x,&y); if(findroot(x)==findroot(y))printf("no\n"); else { printf("yes\n"); Link(x,y); } } else if(ss[1]=='p') { scanf("%d%d",&x,&k); change(x,k); } else { scanf("%d%d",&x,&y); if(findroot(x)!=findroot(y))printf("impossible\n"); else printf("%d\n",getsum(x,y)); } } return 0;}