【BZOJ2002】【HNOI2010】弹飞绵羊 [分块]

弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB
[Submit][Status][Discuss]

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。

Output

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

Sample Input

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

Sample Output

　　2
　　3

HINT

　　对于20%的数据：n,m<=10000;

　　对于100%的数据：n<=200000,m<=100000.

Main idea

　　给定一个位置，走一步可以走到一个指定位置，求走到n以外需要几步，走到的指定位置需要支持修改。

Solution

　　考虑暴力显然不可做，运用分块，维护两个信息：1.走出当前分块需要几步；2.走出当前分块后到了哪个点。

　　每次修改更新改点信息以及该块内的点，又因为一个点不一定只影响到该块内直接跳到这个点的点，也有间接关系的可能性存在，直接倒着搜一遍每次在可以跳到的点+1即可。

Code

  1 #include<iostream>  
  2 #include<algorithm>  
  3 #include<cstdio>  
  4 #include<cstring>  
  5 #include<cstdlib>  
  6 #include<cmath>  
  7 using namespace std;  
  8       
  9 const int ONE=400001;
 10   
 11 int n,Q,P;
 12 int T,x,y;
 13 int num,to;
 14 int a[ONE],To[ONE],F[ONE];
 15 int go,jishu;
 16 int PD[ONE];
 17 int l[ONE],r[ONE];
 18   
 19 struct power
 20 {
 21         int step;
 22         int to;
 23         int from;
 24 }C[ONE];
 25   
 26 int get() 
 27 { 
 28         int res,Q=1;    char c;
 29         while( (c=getchar())<48 || c>57)
 30         if(c=='-')Q=-1;
 31         if(Q) res=c-48; 
 32         while((c=getchar())>=48 && c<=57) 
 33         res=res*10+c-48; 
 34         return res*Q; 
 35 }
 36   
 37 int Query(int x)
 38 {
 39         int j=x;
 40         int Ans=0;
 41         while(j<=n)
 42         {
 43             Ans+=C[j].step;
 44             j=C[j].to;
 45         }
 46         return Ans;
 47 }
 48   
 49 int Update(int x,int y)
 50 {       
 51         int j=x;
 52         To[x]=x+y;
 53         if(To[x]>n) To[x]=n+1;
 54          
 55         jishu=0;
 56         while(C[j].from==C[x].from)
 57         {
 58             j=To[j];
 59             jishu++;
 60         }
 61         C[x].step=jishu; C[x].to=j;
 62          
 63         for(int i=x-1;i>=l[C[x].from];i--)
 64         {
 65             int y=To[i];
 66             if(C[i].from==C[y].from)
 67             {
 68                 C[i].to=C[y].to;
 69                 C[i].step=C[y].step+1;
 70             }
 71         }
 72   
 73 }
 74   
 75 int main()
 76 {      
 77        // freopen("input.in","r",stdin);  
 78        // freopen("input.out","w",stdout);
 79         n=get();
 80         Q=sqrt(n);
 81         for(int i=1;i<=n;i++)
 82         {
 83             a[i]=get(); To[i]=i+a[i];
 84      
 85             if(To[i]>n) To[i]=n+1;
 86             if(!((i-1)%Q))
 87             {
 88                 num++;
 89                 l[num]=i;
 90             }
 91             C[i].from=num; r[num]=i;
 92         }
 93           
 94         for(int i=1;i<=n;i++)
 95         {
 96             int j=i;
 97             jishu=0;
 98             while(C[j].from==C[i].from)
 99             {
100                 j=To[j];
101                 jishu++;
102             }
103             C[i].step=jishu;
104             C[i].to=j;
105             if(C[i].to>n) C[i].to=n+1;
106         }
107           
108         T=get();
109         while(T--)
110         {
111             P=get();
112             if(P==1)
113             {
114                 x=get(); x++;
115                 printf("%d
",Query(x));
116             }
117               
118             if(P==2)
119             {
120                 x=get(); x++;
121                 y=get();
122                 Update(x,y);
123             }
124               
125         }
126 }

View Code