对边界外新建一个点表示，设其后继为自身，则只需维护动态基环内向森林，支持修改点的后继，查询点是否在特定联通块中，若是则查询深度
对每个联通块，必有一个环，任意断掉一条环边，用平衡树维护剩余部分对应的的括号序列，查询深度即为括号序列的前缀和，修改后继时需要分类讨论一下
#include<cstdio> const int N=200007; #define G *++ptr char buf[N*50],*ptr=buf-1; int _(){ int x=0,c=G,f=1; while(c<48)c==‘-‘&&(f=-1),c=G; while(c>47)x=x*10+c-48,c=G; return x*f; } int n,q,ch[N*2][5],nx[N],r1,r2,r3; #define lc ch][0 #define rc ch][1 #define fa ch][2 #define val ch][3 #define sum ch][4 void up(int x){ x[sum]=x[val]+x[lc][sum]+x[rc][sum]; } void rot(int w){ int f=w[fa],d=(w!=f[lc]),g=f[fa]; if(g)g[ch][g[lc]!=f]=w; w[fa]=g; (f[ch][d]=w[ch][d^1])[fa]=f; (w[ch][d^1]=f)[fa]=w; up(f),up(w); } void sp(int x){ while(x[fa]){ int f=x[fa]; if(f[fa])rot((x==f[rc])==(f==f[fa][rc])?f:x); rot(x); } } int gl(int x){ while(x[lc])x=x[lc]; sp(x); return x; } int grt(int x){ int a=x; while(x[fa])x=x[fa]; sp(a); return x; } int mg(int a,int b){ if(!a||!b)return a|b; b=gl(b); (b[lc]=a)[fa]=b; up(b); return b; } void ct_l(int w,int&a,int&b){sp(w);a=w[lc];b=w;a[fa]=w[lc]=0;up(w);} void ct_r(int w,int&a,int&b){sp(w);b=w[rc];a=w;b[fa]=w[rc]=0;up(w);} void lk(int x,int y){ x<<=1;y<<=1; sp(y); if(grt(x)==y)return; ct_r(y,r1,r2); sp(x); mg(mg(r1,x),r2); } void ct(int x){ x<<=1; sp(x); int rt=gl(x); if(x==rt)return; ct_l(x,r1,r2); ct_r(x^1,r2,r3); mg(r1,r3); if(grt(nx[rt>>1]<<1)==r2)lk(rt>>1,nx[rt>>1]); } int get(int x){ x<<=1; sp(x); int r=x[lc][sum]; printf("%d\n",gl(x)==(n+1<<1)?r:-1); } int F(int x){return x>0&&x<=n?x:n+1;} int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; n=_();q=_(); for(int i=1;i<=n;++i)nx[i]=F(i+_()); nx[n+1]=n+1; for(int i=1;i<=n+1;++i){ int l=i<<1,r=l^1; l[val]=1; r[sum]=r[val]=-1; (l[rc]=r)[fa]=l; } for(int i=1;i<=n;++i)lk(i,nx[i]); while(q--){ if(_()==1){ int x=_(); get(x); }else{ int x=_(),y=x+_(); nx[x]=F(y); ct(x); lk(x,nx[x]); } } return 0; }
原文：http://www.cnblogs.com/ccz181078/p/6446010.html