BZOJ 2002 LCT板子题

时间：2020-12-19 15:30:25

思路：

LCT啊...

（分块也行）

不过YOUSIKI出了一道“弹飞大爷” 就不能用分块水过去了

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int fa[N],ch[N][],rev[N],size[N],n,op,q[N],top,a[N],m,xx,yy;

bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}

void push_up(int x){size[x]=size[ch[x][]]+size[ch[x][]]+;}

void push_down(int x){if(rev[x])rev[x]=,rev[ch[x][]]^=,rev[ch[x][]]^=,swap(ch[x][],ch[x][]);}

void rotate(int p){

    int q=fa[p],y=fa[q],f=(ch[q][]==p);

    ch[q][f]=ch[p][!f],fa[ch[q][f]]=q;

    ch[p][!f]=q,fa[p]=y;

    if(!isroot(q)){

        if(ch[y][]==q)ch[y][]=p;

        if(ch[y][]==q)ch[y][]=p;

    }fa[q]=p;push_up(q);

}

void splay(int x){

    q[++top]=x;

    for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];

    while(top)push_down(q[top--]);

    for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])if(!isroot(y)){

        if((ch[y][]==x)^(ch[fa[y]][]==y))rotate(x);

        else rotate(y);

    }push_up(x);

}

void access(int x){for(int t=;x;t=x,x=fa[x])splay(x),ch[x][]=t,push_up(x);}

void makeroot(int x){access(x),splay(x),rev[x]^=;}

void link(int x,int y){makeroot(x),fa[x]=y;}

void cut(int x,int y){makeroot(x),access(y),splay(y);ch[y][]=fa[x]=;}

void split(int x,int y){makeroot(x),access(y),splay(y);}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)link(i,a[i]+i>n?n+:a[i]+i);

    scanf("%d",&m);

    while(m--){

        scanf("%d%d",&op,&xx),xx++;

        if(op==)split(n+,xx),printf("%d\n",size[xx]-);

        else scanf("%d",&yy),cut(xx,xx+a[xx]>n?n+:xx+a[xx]),a[xx]=yy,link(xx,xx+a[xx]>n?n+:xx+a[xx]);

    }

}

相关文章