这道题的lct不想说什么......
这道题是lct的假板子题你需要精简并适当改进LCT给他加上不清真的属性......
#include<cstdio> #include<cstring> #define MAXN 200010 using namespace std; struct spaly { spaly *ch[2],*f; int size; void pushup() { size=ch[1]->size+ch[0]->size+1; } }null[MAXN]; int n,m,a[MAXN]; inline int get(spaly *p) { return p->f->ch[1]==p; } inline bool isroot(spaly *p) { return p->f->ch[0]!=p&&p->f->ch[1]!=p; } inline void rotate(spaly *p) { spaly *fa=p->f,*pa=fa->f; int j=get(p); if(!isroot(fa))pa->ch[get(fa)]=p; if((fa->ch[j]=p->ch[j^1])!=null)fa->ch[j]->f=fa; fa->f=p; p->f=pa; p->ch[j^1]=fa; fa->pushup(); p->pushup(); } inline void Spaly(spaly *p) { for(spaly *fa=p->f;!isroot(p);rotate(p),fa=p->f) if(!isroot(fa)) rotate(get(fa)==get(p)?fa:p); } inline void expose(spaly *p) { spaly *y=null; while(p!=null) { Spaly(p); p->ch[1]=y; p->pushup(); y=p; p=p->f; } } inline void link(spaly *x,spaly *y) { Spaly(x); x->f=y; } inline void cut(spaly *x,spaly *y) { expose(x); Spaly(x); x->ch[0]->f=null; x->ch[0]=null; x->pushup(); } inline void Init() { scanf("%d",&n); null->ch[0]=null->ch[1]=null->f=null; for(int i=1;i<=n;i++) null[i].ch[0]=null[i].ch[1]=null[i].f=null,null[i].size=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(i+a[i]<=n)link(null+i,null+i+a[i]); } } inline void work() { scanf("%d",&m); while(m--) { int opt; scanf("%d",&opt); int x,y; if(opt==1) { scanf("%d",&x); x++; expose(null+x); Spaly(null+x); printf("%d ",null[x].size); } else { scanf("%d%d",&x,&y); x++; expose(null+x); Spaly(null+x); if(null[x].size!=1)cut(null+x,null+x+a[x]); a[x]=y; if(x+y<=n)link(null+x,null+x+y); } } } int main() { Init(); work(); return 0; }