首页 > 代码库 > BZOJ2002 [Hnoi2010]Bounce 弹飞绵羊
BZOJ2002 [Hnoi2010]Bounce 弹飞绵羊
一眼题，LCT。
然后悲剧的发现不会写，只好分块来做。
令s = sqrt(n)，那么先分成s块，每块s个弹簧。
现在让每个点记录两个值，cnt和to，分别表示弹到这个块外面的次数和弹到了哪里。
我们发现单点修改只要修改块内元素，时间复杂度是O(s)的；而单点查询要查他后面的所有块，时间复杂度也是O(s)的，
于是总的复杂度是O(Q * logn)，解决！
1 /************************************************************** 2 Problem: 2002 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1736 ms 7 Memory:5700 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 16 int n, m, T, tot;17 int w[250000], cnt[250000], to[250000], block[250000], a[250000];18 19 void build(){20 int x = tot = 0, y;21 while (x < n){22 x += T, ++tot;23 w[tot] = x;24 }25 w[tot] = min(n, w[tot]);26 27 for (int i = tot; i >= 1; --i)28 for (int x = w[i]; x > w[i - 1]; --x){29 y = x + a[x];30 if (y <= w[i])31 to[x] = to[y], cnt[x] = cnt[y] + 1;32 else to[x] = y, cnt[x] = 1;33 block[x] = i;34 }35 }36 37 int query(int x){38 int res = 0;39 while (x <= n)40 res += cnt[x], x = to[x];41 return res;42 }43 44 void change(int x){45 int B = block[x], y;46 for (int i = x; i > w[B - 1]; --i){47 y = i + a[i];48 if (y <= w[B])49 to[i] = to[y], cnt[i] = cnt[y] + 1;50 else to[i] = y, cnt[i] = 1;51 }52 }53 54 int main(){55 scanf("%d", &n);56 for (int i = 1; i <= n; ++i)57 scanf("%d", a + i);58 T = (int) sqrt(n);59 build();60 61 scanf("%d", &m);62 int X, Y, Z;63 while (m--){64 scanf("%d%d", &X, &Y);65 if (X == 1)66 printf("%d\n", query(Y + 1));67 else {68 scanf("%d", &Z);69 a[Y + 1] = Z;70 change(Y + 1);71 }72 }73 return 0;74 }
（p.s. 从0开始坑死人啊。。。。）
BZOJ2002 [Hnoi2010]Bounce 弹飞绵羊
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。