弹飞绵羊

题目描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入输出格式

输入格式：

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

输入样例#1：

输出样例#1：

2

3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

　　分析：

　　把每个装置看作一个点，然后连边，每次修改弹力值就可以看作断边和连边，可以用LCT维护。那么查询显然就直接求该点原树到根节点的距离。维护的时候比较方便，很多函数都可以省略。

　　Code：

//It is made by HolseLee on 30th June 2018

//Luogu.org P3203

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

int n,m,a[N],fa[N],s[N],ch[N][];

inline int read()

{

    char ch=getchar();int num=;bool flag=false;

    while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

    while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

    return flag?-num:num;

}

inline void pushup(int x)

{

    s[x]=s[ch[x][]]+s[ch[x][]]+;

}

inline bool isroot(int x)

{

    return (ch[fa[x]][]!=x)&&(ch[fa[x]][]!=x);

}

inline void rotate(int x)

{

    int y=fa[x],z=fa[y];

    int k=(ch[y][]==x);

    int w=ch[x][k^];

    if(!isroot(y))ch[z][ch[z][]==y]=x;

    ch[x][k^]=y;ch[y][k]=w;

    if(w)fa[w]=y;fa[y]=x;fa[x]=z;

    pushup(y);

}

inline void splay(int x)

{

    while(!isroot(x)){

        int y=fa[x],z=fa[y];

        if(!isroot(y))

        ((ch[y][]==x)^(ch[z][]==y))?

        rotate(y):rotate(x);

        rotate(x);}

    pushup(x);

}

inline void access(int x)

{

    for(int y=;x;x=fa[y=x])

    splay(x),ch[x][]=y,pushup(x);

}

int main()

{

    n=read();int x,y,z;

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

        s[i]=;x=read();

        if(i+x<=n)fa[i]=i+x;}

    m=read();

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

        x=read();y=read();

        if(x==){

            ++y;

            access(y);splay(y);

            printf("%d\n",s[y]);

        }

        else{

            z=read();++y;

            access(y);splay(y);

            ch[y][]=fa[ch[y][]]=;

            if(y+z<=n)fa[y]=y+z;

            pushup(y);}

    }

    return ;

}

巴特西

洛谷P3203 [HNOI2010] 弹飞绵羊 [LCT]

弹飞绵羊

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章