[Hnoi2010]Bounce 弹飞绵羊

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

Sample Output

2
3


  1. 看了题目很就可以想到，完全根据题意暴力过去，查询一次的时间复杂度为O(n), 修改一次的复杂度为 0（1），一共查询 m 次， 总共时间复杂度就是O（n*m），这样显然会超时；
  2. 想一下，能不能优化一下查询的时间复杂度，可以维护一个组数b[i]，表示在位置 i 时要弹跳的次数，这样查询一次的时间复杂度为O（1），然而修改后每次要维护数组b[i]的时间复杂度变成了O(n)，总共时间复杂度还是是O（n*m）；（每次维护时只要维护第一个点到这个点的值，因为这个点的维护不会影响后面的点）
  3.查询 和 修改 时间复杂度可以达到O(1),可是相对应的修改和查询的时间复杂度却变成了O（n），可以均衡一下，将数组分成sqrt（n）块，每次维护数组只需要维护当前块，每次查询只需要查询sqrt（n）块，这样查询和修改的时间复杂度都变成了O( sqrt(n) ),总共时间复杂度为 O( sqtr(n)*m );

 1 #include<cstdio> 
 2 #include<cmath> 
 3 using namespace std; 
 4 int a[200010]; 
 5 int b[200010]; 
 6 int pos[200010]; 
 7 int function(int a,int b) 
 8 { 
 9     if(a%b) return 1; 
10     return 0; 
11 } 
12 int main (void) 
13 { 
14     int n; scanf("%d", &n); 
15     for(int i = 0; i < n; i++) 
16         scanf("%d",&a[i]); 
17     int sq = sqrt(n); 
18     int num = sq + function(n, sq); 
19     for(int i = num; i >= 1; i--) 
20     { 
21         int j = i*sq-1;  
22         if(i==num) j=n-1; 
23         int lim = j; 
24         for(; j >= (i-1)*sq; j--) 
25         { 
26             if( a[j] + j <= lim) b[j] = b[a[j]+j] + 1, pos[j] = pos[a[j]+j] ; 
27             else b[j] = 1, pos[j] = a[j]+j; 
28         } 
29     } 
30     int m; scanf("%d", &m); 
31     while(m--) 
32     { 
33         int i, j; scanf("%d%d",&i,&j); 
34         if(i==1) 
35         { 
36             int id = j; 
37             int ans = 0; 
38             while(id < n) 
39             { 
40                 ans += b[id], id = pos[id]; 
41             } 
42             printf("%d
",ans); 
43         } 
44         else
45         { 
46             int k; scanf("%d",&k); 
47             int nu = ((j+1)/sq) + function(j+1, sq); 
48             a[j] = k; 
49             int x = nu*sq-1;  
50             if(nu==num) x=n-1; 
51             int lim = x; 
52             for(; j >= (nu-1)*sq; j--) 
53             { 
54                 if( a[j] + j <= lim) b[j] = b[a[j]+j] + 1, pos[j] = pos[a[j]+j] ; 
55                 else b[j] = 1, pos[j] = a[j]+j; 
56             } 
57         }    
58     }    
59 }  
60   
61