[HNOI2010]弹飞绵羊

题目描述

某天，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动态树模板练手（调了好久）

初始时每一个点都是一个LCT，然后将每一个点和它的下一个节点连起来。（link）

对于修改，我们将这个节点和它下一个节点断开（cut），然后link一下它和新的下一个节点。

对于查询，每次找到这个点（access），然后旋到根（splay），输出它左子树的大小就好。

  1 //Never forget why you start
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<algorithm>
  8 #define ll(x) lct[x].child[0]
  9 #define rr(x) lct[x].child[1]
 10 #define son(x,t) lct[x].child[t]
 11 using namespace std;
 12 int n,m,len[200005];
 13 struct LCT{
 14   int child[2],fa,rev,size;
 15   bool is_root;
 16 }lct[200005];
 17 void push_up(int x){
 18   lct[x].size=lct[ll(x)].size+lct[rr(x)].size+1;
 19 }
 20 void push_rev(int x){
 21   if(!x)return;
 22   swap(ll(x),rr(x));
 23   lct[x].rev^=1;
 24 }
 25 void push_down(int x){
 26   if(lct[x].rev){
 27     push_rev(ll(x));
 28     push_rev(rr(x));
 29     lct[x].rev^=1;
 30   }
 31 }
 32 int getson(int root){
 33   return root==son(lct[root].fa,1);
 34 }
 35 void push(int x){
 36   if(!lct[x].is_root)push(lct[x].fa);
 37   push_down(x);
 38 }
 39 void rotate(int x){
 40   if(lct[x].is_root)return;
 41   int fa=lct[x].fa,fafa=lct[fa].fa,t=getson(x);
 42   son(fa,t)=son(x,!t);if(son(x,!t))lct[son(x,!t)].fa=fa;
 43   lct[fa].fa=x;son(x,!t)=fa;
 44   lct[x].fa=fafa;
 45   if(!lct[fa].is_root)son(fafa,son(fafa,1)==fa)=x;
 46   else lct[x].is_root=1,lct[fa].is_root=0;
 47   push_up(fa);
 48   push_up(x);
 49 }
 50 void splay(int x){
 51   push(x);
 52   for(int fa;!lct[x].is_root;rotate(x))
 53     if(!lct[fa=lct[x].fa].is_root)
 54       rotate(getson(fa)==getson(x)?fa:x);
 55 }
 56 void access(int x){
 57   int y=0;
 58   do{
 59     splay(x);
 60     lct[rr(x)].is_root=1;
 61     lct[rr(x)=y].is_root=0;
 62     push_up(x);
 63     x=lct[y=x].fa;
 64   }while(x);
 65 }
 66 void mroot(int x){
 67   access(x);
 68   splay(x);
 69   push_rev(x);
 70 }
 71 void link(int u,int v){
 72   if(v>n)v=n+1;
 73   mroot(u);
 74   lct[u].fa=v;
 75 }
 76 void cut(int u,int v){
 77   if(v>n)v=n+1;
 78   mroot(u);
 79   access(v);splay(v);
 80   lct[son(v,0)].fa=lct[v].fa;
 81   lct[son(v,0)].is_root=1;
 82   son(v,0)=lct[v].fa=0;
 83   push_up(v);
 84 }
 85 int main(){
 86   freopen("1.in","r",stdin);
 87   int i,j;
 88   scanf("%d",&n);
 89   for(i=1;i<=n+1;i++){
 90     lct[i].child[0]=lct[i].child[1]=lct[i].fa=0;
 91     lct[i].size=lct[i].is_root=1;
 92   }
 93   for(i=1;i<=n;i++){
 94     scanf("%d",&len[i]);
 95     link(i,i+len[i]);
 96   }
 97   scanf("%d",&m);
 98   for(i=1;i<=m;i++){
 99     int a,b,c;
100     scanf("%d%d",&a,&b);
101     b++;
102     if(a==1){
103       mroot(n+1);
104       access(b);
105       splay(b);
106       printf("%d
",lct[ll(b)].size);
107     }
108     else{
109       scanf("%d",&c);
110       cut(b,b+len[b]);
111       link(b,b+c);
112       len[b]=c;
113     }
114   }
115   return 0;
116 }