bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊 動態樹

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 4055  Solved: 2172
[Submit][Status]

Description

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

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

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

Sample Input

4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

2
3

HINT

 

 

　　第一次編LCT，主要還是照着網上的標程在編，LCT的主體思路是對於每一個鏈維護一個splay，而非常巧妙的地方是splay的pnt[]指針，對於當前鏈上對應根節點，pnt指針等同於樹鏈剖分中的top指針，這樣可以巧妙地維護splay森林中每一顆子樹所代表的鏈的關係。

　　這個LCT支持樹的刪邊加邊。

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 310000
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
//AC
typedef long long qword;
inline int nextInt()
{
        char ch;
        int x=0;
        bool flag=false;
        do
                ch=(char)getchar(),flag=(ch=='-')?true:flag;
        while(ch<'0'||ch>'9');
        do x=x*10+ch-'0';
        while (ch=(char)getchar(),ch<='9' && ch>='0');
        return x*(flag?-1:1);
}

int n,m;
int ch[MAXN][2],pnt[MAXN];
int siz[MAXN];
bool rt[MAXN];
bool is_root(int cur)
{
        return pnt[cur]==0 || (cur!=ch[pnt[cur]][0] && cur!=ch[pnt[cur]][1]);
}

void push_up(int cur)
{
        siz[cur]=siz[ch[cur][0]]+siz[ch[cur][1]]+1;
}
void rotate(int cur)
{
        int p=pnt[cur],anc=pnt[p];
        int dir=ch[p][0]==cur;
        if (!is_root(p))
                ch[anc][ch[anc][1]==p]=cur;

        pnt[cur]=anc;
        pnt[ch[cur][dir]]=p;
        ch[p][1-dir]=ch[cur][dir];
        ch[cur][dir]=p;
        pnt[p]=cur;
        push_up(p);
        push_up(cur);
}

//int stack[MAXN];
void splay(int cur)
{
        int now;
        /*
        int tops=-1;
        now=cur;
        while (pnt[now])
                stack[++tops]=now;
        int i;
        for (i=tops;i>=0;i--)
                push_down(i);
                *///本題不用打標記
        while (!is_root(cur))
        {
                int p=pnt[cur],anc=pnt[p];
                if (is_root(pnt[cur]))
                        rotate(cur);
                else if ( (ch[p][1]==cur) == (ch[anc][1]==p) )
                        rotate(p),rotate(cur);//Attention!
                else 
                        rotate(cur),rotate(cur);
        }
        push_up(cur);
}
void Access(int cur)
{
        int son=0;
        for (;cur;cur=pnt[son=cur])
        {
                splay(cur);
                ch[cur][1]=son;
                push_up(cur);
        }
}
int a[MAXN];
int main()
{
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
        int i,j,k;
        int x,y,z;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
                scanf("%d",&a[i]);
        }
        for (i=1;i<=n;i++)
                siz[i]=1;
        siz[n+1]=1;
        for (i=1;i<=n;i++)
        {
                int t=i+a[i];
                if (t>n+1)t=n+1;
                pnt[i]=t;//初始化時不存在重鏈
        }
        scanf("%d",&m);
        int opt;
        while (m--)
        {
                scanf("%d",&opt);
                if (opt==1)
                {
                        scanf("%d",&x);
                        x++;//編號從0開始
                        Access(x);
                        splay(x);//保證siz[x]包含整棵子樹
                        printf("%d
",siz[x]-1);
                        //printf("%d
",siz[ch[x][0]]); 二者等價
                }else
                {
                        scanf("%d%d",&x,&y);
                        x++;
                        Access(x);
                        splay(x);//意味着ch[x][1]==null
                        //此時pnt[x]不在這顆splay上
                        pnt[ch[x][0]]=pnt[x];
                        pnt[x]=0;
                        ch[x][0]=0;
                        push_up(x);//對於x即其子節點有所改動時使用
                        int t=x+y;;
                        if (t>n+1)t=n+1;
                        pnt[x]=t;
                }
        }
        return 0;
}