Codeforces Beta Round #13 E. Holes 分块

链接：

http://codeforces.com/contest/13/problem/E

题意：

有n个洞，每个洞有一个power值，表示进入这个洞的球能够被弹到i+power处，两种操作

1.将a洞的power改为b

2.询问从洞a开始放一个球，能被弹出的次数和最终位置

题解：

分块处理，每个块中处理每个点被弹出这个块的位置和次数。

开始分成了sqrt(n)块，结果超时了，改成sqrt(2*n)，就过了

代码：

 31 int n, m;
 32 int a[MAXN];
 33 PII Block[MAXN];
 34 int L[MAXN], R[MAXN], Belong[MAXN];
 35 
 36 void init() {
 37     int cap = sqrt(2*n);
 38     int num = n / cap;
 39     if (n%cap != 0) num++;
 40     rep(i, 1, n + 1) Belong[i] = (i - 1) / cap + 1;
 41     rep(i, 1, num + 1) {
 42         L[i] = (i - 1)*cap + 1;
 43         R[i] = i*cap;
 44     }
 45     R[num] = n;
 46     rep(i, 1, num + 1) per(j, L[i], R[i] + 1) {
 47         if (j + a[j] > R[i]) {
 48             Block[j].first = j + a[j];
 49             Block[j].second = 1;
 50         }
 51         else {
 52             Block[j] = Block[j + a[j]];
 53             Block[j].second++;
 54             if (Block[j].first > R[i]) {
 55                 Block[j].first = j + a[j];
 56                 Block[j].second--;
 57             }
 58         }
 59     }
 60 }
 61 
 62 void update(int x, int y) {
 63     a[x] = y;
 64     int id = Belong[x];
 65     per(j, L[id], R[id] + 1) {
 66         if (j + a[j] > R[id]) {
 67             Block[j].first = j + a[j];
 68             Block[j].second = 1;
 69         }
 70         else {
 71             Block[j] = Block[j + a[j]];
 72             Block[j].second++;
 73             if (Block[j].first > R[id]) {
 74                 Block[j].first = j + a[j];
 75                 Block[j].second--;
 76             }
 77         }
 78     }
 79 }
 80 
 81 PII query(int x) {
 82     int id = Belong[x];
 83     PII res = mp(0, 0);
 84     while (x <= n) {
 85         res.first = x;
 86         res.second += Block[x].second;
 87         if (x == Block[x].first) break;
 88         x = Block[x].first;
 89     }
 90     return res;
 91 }
 92 
 93 int main() {
 94     ios::sync_with_stdio(false), cin.tie(0);
 95     cin >> n >> m;
 96     rep(i, 1, n + 1) cin >> a[i];
 97     init();
 98     while (m--) {
 99         int op, x, y;
100         cin >> op >> x;
101         if (op) {
102             PII ans = query(x);
103             cout << ans.first << ' ' << ans.second << endl;
104         }
105         else {
106             cin >> y;
107             update(x, y);
108         }
109     }
110     return 0;
111 }