题解-弹飞绵羊 (HNOI2015)

LCT 模板题，分块也很优秀。

分块做法

维护每个点到第一次跳到下一个块时的跳跃次数，并记录其跳到下一个块的第一个点。

注意常见的分块玄学操作 n = min(sqrt(N), 100) 和 n = sqrt(N)*1.23 。

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <math.h>
 4 
 5 using namespace std;
 6 
 7 const int _N = 220000;
 8 
 9 int N, n, M;
10 int A[_N], f[_N], des[_N];
11 
12 inline int dn(int v) { return (v-1)/n*n+1; }
13 
14 inline int up(int v) { return min(N, (v-1)/n*n+n); }
15 
16 int main()
17 {
18     int i;
19     scanf("%d", &N);
20     for (i = 1; i <= N; ++i)
21         scanf("%d", &A[i]);
22     scanf("%d", &M);
23     
24     n = min(N, int(sqrt(N+0.5)*1.32));
25     
26     for (i = N; i >= 1; --i)
27         if (i+A[i] > up(i)) f[i] = 1, des[i] = min(i+A[i], N+1);
28         else f[i] = f[i+A[i]]+1, des[i] = des[i+A[i]];
29     
30     for (i = 1; i <= M; ++i) {
31         int ins, k;
32         scanf("%d%d", &ins, &k), ++k;
33         if (ins == 1) {
34             int cnt = 0, j = k;
35             while (j != N+1) {
36                 cnt += f[j];
37                 j = des[j];
38             }
39             printf("%d
", cnt);
40         } else {
41             int j = k;
42             scanf("%d", &A[k]);
43             for (int t = j; t >= dn(j); --t)
44                 if (t+A[t] > up(t)) f[t] = 1, des[t] = min(t+A[t], N+1);
45                 else f[t] = f[t+A[t]]+1, des[t] = des[t+A[t]];
46         }
47     }
48     
49     return 0;
50 }

View Code

LCT做法

  1 #include <stdio.h>
  2 #include <stack>
  3 
  4 using namespace std;
  5 
  6 const int _N = 220000;
  7 
  8 typedef long long LL;
  9 
 10 stack<LL> S;
 11 LL Sum[_N], L[_N], R[_N], Dad[_N], Rev[_N], J[_N], W[_N];
 12 
 13 inline void Update(LL x) { Sum[x] = Sum[L[x]] + W[x] + Sum[R[x]]; return; }
 14 
 15 inline bool IsRoot(LL x) { return L[Dad[x]] != x && R[Dad[x]] != x; }
 16 
 17 void Zig(LL x)
 18 {
 19     LL y = Dad[x], z = Dad[y];
 20     if (!IsRoot(y)) L[z] == y ? L[z] = x : R[z] = x;
 21     Dad[x] = z;
 22     L[y] = R[x], Dad[R[x]] = y;
 23     R[x] = y, Dad[y] = x;
 24     Update(y), Update(x);
 25     return;
 26 }
 27 
 28 void Zag(LL x)
 29 {
 30     LL y = Dad[x], z = Dad[y];
 31     if (!IsRoot(y)) L[z] == y ? L[z] = x : R[z] = x;
 32     Dad[x] = z;
 33     R[y] = L[x], Dad[L[x]] = y;
 34     L[x] = y, Dad[y] = x;
 35     Update(y), Update(x);
 36     return;
 37 }
 38 
 39 inline void PushDown(LL x) {
 40     if (Rev[x]) {
 41         Rev[L[x]] ^= 1, Rev[R[x]] ^= 1, Rev[x] ^= 1;
 42         swap(L[x], R[x]);
 43     }
 44     return;
 45 }
 46 
 47 void Splay(LL x)
 48 {
 49     S.push(x);
 50     for (LL i = x; !IsRoot(i); i = Dad[i]) S.push(Dad[i]);
 51     while (!S.empty()) PushDown(S.top()), S.pop();
 52     
 53     while (!IsRoot(x)) { 
 54         LL y = Dad[x], z = Dad[y];
 55         if (!IsRoot(y)) {
 56             if (L[z] == y) L[y] == x ? (Zig(y), Zig(x)) : (Zag(x), Zig(x));
 57             else R[y] == x ? (Zag(y), Zag(x)) : (Zig(x), Zag(x));
 58         } else {
 59             L[y] == x ? Zig(x) : Zag(x);
 60         }
 61     }
 62     
 63     return;
 64 }
 65 
 66 void Access(LL x)
 67 {
 68     LL t = 0;
 69     while (x) {
 70         Splay(x), R[x] = t, Update(x);
 71         t = x, x = Dad[x];
 72     }
 73     return;
 74 }
 75 
 76 LL FindRoot(LL x) { Access(x), Splay(x); while (L[x]) x = L[x]; return x; }
 77 
 78 void MakeRoot(LL x) { Access(x), Splay(x), Rev[x] ^= 1; return; }
 79 
 80 void Cut(LL x, LL y) { MakeRoot(x), Access(y), Splay(y), L[y] = Dad[x] = 0; Update(y); return; }
 81 
 82 void Link(LL x, LL y) { MakeRoot(x), Dad[x] = y; }
 83 
 84 int main()
 85 {
 86 //    freopen("1.txt", "r", stdin);
 87     LL N, Q, i, Suicide;
 88     scanf("%lld", &N), Suicide = N+1;
 89 //    W[Suicide] = Sum[Suicide] = 1;
 90     for (i = 1; i <= N; ++i) scanf("%lld", &J[i]), W[i] = 1, Sum[i] = 1;
 91     for (i = 1; i <= N; ++i)
 92         if (i+J[i] <= N) Link(i, i+J[i]);
 93         else Link(i, Suicide);
 94     
 95     scanf("%lld", &Q);
 96     while (Q--) {
 97         LL ins, t1, t2;
 98         scanf("%lld%lld", &ins, &t1), ++t1;
 99         if (ins == 1) {
100             MakeRoot(Suicide), Access(t1), Splay(t1);
101             printf("%lld
", Sum[t1]);
102         } else if (ins == 2) {
103             scanf("%lld", &t2);
104             if (t1+J[t1] <= N) Cut(t1, t1+J[t1]);
105             else Cut(t1, Suicide);
106             J[t1] = t2;
107             if (t1+J[t1] <= N) Link(t1, t1+J[t1]);
108             else Link(t1, Suicide);
109         }
110     }
111     return 0;
112 }

View Code

NKOJ2381

P2381【HNOI2010】弹飞绵羊

时间限制 : 10000 MS 空间限制 : 265536 KB

问题描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入格式

第一行包含一个整数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

输出格式

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

样例输入

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

样例输出

2
3

来源 HZOI