【BZOJ2002】 [Hnoi2010]Bounce 弹飞绵羊分块-布布扣-bubuko.com

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

Source

　　强行用分块做，算是另一种分块的用法，分块真奇妙啊。

　　受到了来自abclzr的细心教导，首先思考最普通的模拟，发现可以O(n)路径压缩，O(1)的查询，但是需要修改就变成了O（n^2）的修改，于是考虑分块，记录一下每个点跳出该点所在的块的步数，也就是在每块内进行路径压缩，还有记录每个点跳出块后到达的点，同样可以块内路径压缩完成，这样就变成了O(sqrt(n))的修改和查询，但是预处理是O(n*sqrt(n))的，虽然可以过，但是LCT更快啦啦，我偏要写分块啦啦,读入优化背了一晚上WA的锅啦啦啦MD。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #define N 200010
 7 using namespace std;
 8 int pos[N],st[N],nx[N],k[N];
 9 int n,m,q,block;
10 inline int read ()
11 {
12     char c;
13     int ans=0;
14     while ((c=getchar())==‘\n‘ || c==‘ ‘ || c==‘\r‘);
15     ans=c-‘0‘;
16     while (isdigit(c=getchar())) ans=ans*10+c-‘0‘;
17     return ans;
18 } 
19 int solve(int x)
20 {
21     int ans=0;
22     while (1)
23     {
24         ans+=st[x];
25         if (!nx[x])    return ans;
26         x=nx[x];
27     }
28 }
29 int main()
30 {
31     n=read();
32     block=(int)(sqrt(n));
33     for (int i=1;i<=n;i++)
34     {
35         pos[i]=(i-1)/block+1;
36         k[i]=read();
37     }
38     for (int i=n;i>=1;i--)
39     {
40         if (i+k[i]>n)    st[i]=1;
41         else if (pos[i]==pos[i+k[i]])
42              {
43                  st[i]=st[i+k[i]]+1;
44                  nx[i]=nx[i+k[i]];
45              }
46         else
47             {
48                 st[i]=1;
49                 nx[i]=i+k[i];
50             }
51     }
52     q=read();
53     for (int i=1;i<=q;i++)
54     {
55         int x,y,z;
56         x=read();y=read();
57         y++;
58         if (x==1) printf("%d\n",solve(y));
59         else
60         {
61         z=read();
62             k[y]=z;
63             for (int j=y;j>=(pos[y]-1)*block+1;j--)
64             {
65                 if (j+k[j]>n)    st[j]=1,nx[j]=0;
66                 else if (pos[j]==pos[j+k[j]])
67                      {
68                          st[j]=st[j+k[j]]+1;
69                          nx[j]=nx[j+k[j]];
70                      }
71                      else    
72                      {
73                          st[j]=1;
74                          nx[j]=j+k[j];
75                      }    
76             }
77         }
78     }
79     return 0;
80 }

View Code

【BZOJ2002】 [Hnoi2010]Bounce 弹飞绵羊分块

原文：http://www.cnblogs.com/DMoon/p/5267583.html

【BZOJ2002】 [Hnoi2010]Bounce 弹飞绵羊 分块