bzoj4764: 弹飞大爷

Description

自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们

决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了

第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也

就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替

换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会

把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察

，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位

置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。

Input

第一行为两个整数N和M，代表序列长度和操作次数。

第二行为N个整数，代表初始的小伙伴序列。

接下来有M行，每行代表一个操作。

如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹

起会摔在地上。如果永远不会摔在地上，请输出-1。

如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。

N,M <= 200000 |Ai| < N

Output

对于每次询问操作，输出弹起次数或-1。

对边界外新建一个点表示，设其后继为自身，则只需维护动态基环内向森林，支持修改点的后继，查询点是否在特定联通块中，若是则查询深度

对每个联通块，必有一个环，任意断掉一条环边，用平衡树维护剩余部分对应的的括号序列，查询深度即为括号序列的前缀和，修改后继时需要分类讨论一下

#include<cstdio>

const int N=;

#define G *++ptr

char buf[N*],*ptr=buf-;

int _(){

    int x=,c=G,f=;

    while(c<)c=='-'&&(f=-),c=G;

    while(c>)x=x*+c-,c=G;

    return x*f;

}

int n,q,ch[N*][],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^])[fa]=f;

    (w[ch][d^]=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]=;up(w);}

void ct_r(int w,int&a,int&b){sp(w);b=w[rc];a=w;b[fa]=w[rc]=;up(w);}

void lk(int x,int y){

    x<<=;y<<=;

    sp(y);

    if(grt(x)==y)return;

    ct_r(y,r1,r2);

    sp(x);

    mg(mg(r1,x),r2);

}

void ct(int x){

    x<<=;

    sp(x);

    int rt=gl(x);

    if(x==rt)return;

    ct_l(x,r1,r2);

    ct_r(x^,r2,r3);

    mg(r1,r3);

    if(grt(nx[rt>>]<<)==r2)lk(rt>>,nx[rt>>]);

}

int get(int x){

    x<<=;

    sp(x);

    int r=x[lc][sum];

    printf("%d\n",gl(x)==(n+<<)?r:-);

}

int F(int x){return x>&&x<=n?x:n+;}

int main(){

    buf[fread(buf,,sizeof(buf),stdin)]=;

    n=_();q=_();

    for(int i=;i<=n;++i)nx[i]=F(i+_());

    nx[n+]=n+;

    for(int i=;i<=n+;++i){

        int l=i<<,r=l^;

        l[val]=;

        r[sum]=r[val]=-;

        (l[rc]=r)[fa]=l;

    }

    for(int i=;i<=n;++i)lk(i,nx[i]);

    while(q--){

        if(_()==){

            int x=_();

            get(x);

        }else{

            int x=_(),y=x+_();

            nx[x]=F(y);

            ct(x);

            lk(x,nx[x]);

        }

    }

    return ;

}

巴特西

bzoj4764: 弹飞大爷

Description

Input

Output

最新文章

热门文章