Skip to content

「HNOI2010」弹飞绵羊

题解约 1.2 千字
# 洛谷 # BZOJ # 数据结构 # HNOI # 2010 # 动态树 # Link-Cut Tree # Splay
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 nn 个装置，每个装置设定初始弹力系数 kik_i，当绵羊达到第 ii 个装置时，它会往后弹 kik_i 步，达到第 i+kii + k_i 个装置，若不存在第 i+kii + k_i 个装置，则绵羊被弹飞。

绵羊想知道当它从第 ii 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

#输入格式

第一行包含一个整数 nn，表示地上有 nn 个装置，装置的编号从 0∼n−10 \sim n - 1。

接下来一行有 nn 个正整数，依次为那 nn 个装置的初始弹力系数。

第三行有一个正整数 mm，表示操作次数。接下来 mm 行每行至少有两个数 i,ji,j。

  • 若 i=1i = 1，你要输出从 jj 出发被弹几次后被弹飞；
  • 若 i=2i = 2，则还会再输入一个正整数 kk，表示第 jj 个弹力装置的系数被修改成 kk。

#输出格式

对于每个 i=1i = 1 的操作，输出一行一个整数表示答案。

#输入输出样例

样例输入 #1

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

样例输出 #1

2
3

#数据范围与约定

对于 20%20\% 的数据，1≤n,m≤1041 \le n, m \le 10^4；
对于 100%100\% 的数据，1≤n≤2×1051 \le n \le 2 \times 10^5，1≤m≤1051 \le m \le 10^5。

#思路

首先将题中给的所有编号 +1+ 1 方便计算。

设节点 n+1n + 1 为终点，从所有可以弹飞的点连一条边到这个点上，就可以用 LCT 来求出路径上的节点数了。也有作为森林维护的方法，此处不再做过多说明。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
#include <stack>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m, a[N];

class LinkCutTree {
  private:
    struct node {
        size_t l, r, f;
        unsigned s;
        bool rev;

        node()
            : l(0), r(0), f(0), s(0), rev(false) {}

        node(size_t _f)
            : l(0), r(0), f(_f), s(1), rev(false) {}

        size_t &child(unsigned x) {
            return !x ? l : r;
        }
    } tr[N];

    inline void pushup(size_t u) {
        tr[u].s = tr[tr[u].l].s + 1 + tr[tr[u].r].s;
    }

    inline void pushdown(const size_t &u) {
        if (!tr[u].rev) return;

        std::swap(tr[u].l, tr[u].r);
        tr[tr[u].l].rev = !tr[tr[u].l].rev;
        tr[tr[u].r].rev = !tr[tr[u].r].rev;
        tr[u].rev = false;
    }

    unsigned relation(const size_t &u) {
        return u == tr[tr[u].f].l ? 0 : 1;
    }

    bool isRoot(const size_t &u) {
        return tr[tr[u].f].l != u && tr[tr[u].f].r != u;
    }

    void rotate(size_t u) {
        size_t p = tr[u].f;
        unsigned x = relation(u);

        if (!isRoot(p)) {
            tr[tr[p].f].child(relation(p)) = u;
        }
        tr[u].f = tr[p].f;

        if (tr[u].child(x ^ 1)) {
            tr[tr[u].child(x ^ 1)].f = p;
        }
        tr[p].child(x) = tr[u].child(x ^ 1);

        tr[u].child(x ^ 1) = p;
        tr[p].f = u;

        pushup(p);
        pushup(u);
    }

    void splay(size_t u) {
        std::stack<size_t> st;

        size_t cur = u;
        st.push(cur);
        while (!isRoot(cur)) {
            st.push(tr[cur].f);
            cur = tr[cur].f;
        }

        while (!st.empty()) {
            pushdown(st.top());
            st.pop();
        }

        while (!isRoot(u)) {
            if (isRoot(tr[u].f)) {
                rotate(u);
            } else if (relation(u) == relation(tr[u].f)) {
                rotate(tr[u].f);
                rotate(u);
            } else {
                rotate(u);
                rotate(u);
            }
        }
    }

    void access(size_t u) {
        for (size_t f = 0; u; u = tr[f = u].f) {
            splay(u);
            tr[u].r = f;
            pushup(u);
        }
    }

    void makeRoot(const size_t &u) {
        access(u);
        splay(u);
        tr[u].rev = !tr[u].rev;
    }

    size_t findRoot(size_t u) {
        access(u);
        splay(u);

        while (tr[u].l) {
            u = tr[u].l;
        }

        return u;
    }

    void split(const size_t &x, const size_t &y) {
        makeRoot(x);
        access(y);
        splay(y);
    }

  public:
    unsigned query(int x, int y) {
        split(x, y);

        return tr[y].s;
    }

    void link(const int &x, const int &y) {
        makeRoot(x);

        if (findRoot(y) != x) {
            tr[x].f = y;
        }
    }

    void cut(int x, int y) {
        split(x, y);

        if (tr[y].l == x) {
            tr[y].l = 0;
            tr[x].f = 0;
        }
    }
} lct;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        lct.link(i, std::min(i + a[i], n + 1));
    }

    cin >> m;

    while (m--) {
        int op, x, y;

        cin >> op;

        if (op == 1) {
            cin >> x;

            cout << lct.query(x + 1, n + 1) - 1 << endl;
        } else {  // op == 2
            cin >> x >> y;

            x++;
            lct.cut(x, std::min(x + a[x], n + 1));
            lct.link(x, std::min(x + (a[x] = y), n + 1));
        }
    }

    return 0;
}