「BZOJ-2002」[Hnoi2010]Bounce 弹飞绵羊-Link-Cut Tree

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

链接

BZOJ-2002

题解

对于每一个 $i$,建边 $(i, i + k_i)$,形成的一定是一棵树,修改弹力系数,就相当于在 $LCT$ 上先 $cut$ 原边然后再 $link$ 新边,而询问弹几次会弹飞则是询问左子树的大小。所以在 $splay$ 中维护一下子树大小就好了。

代码

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
/*
* created by xehoth on 24-03-2017
*/
#include <bits/stdc++.h>
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline void read(T &x) {
static char c;
static bool iosig;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == -1) return;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
namespace LinkCutTree {
const int MAXN = 200010;
struct Node *null;
struct Node {
Node *c[2], *fa;
bool rev;
Node *top;
int size;
Node() : fa(null), top(NULL), size(1) {
c[0] = c[1] = null;
}
inline void maintain() {
size = c[0]->size + c[1]->size + 1;
}
inline void reverse() {
rev ^= 1, std::swap(c[0], c[1]);
}
inline void pushDown() {
rev ? c[0]->reverse(), c[1]->reverse(), rev = false : 0;
}
inline bool relation() {
return this == fa->c[1];
}
inline void rotate(bool f) {
Node *o = fa;
top = o->top;
o->pushDown(), pushDown();
(fa = o->fa)->c[o->relation()] = this;
(o->c[f] = c[!f])->fa = o;
(c[!f] = o)->fa = this;
o->maintain();
}
inline void splay() {
Node *o = fa;
bool f;
for (pushDown(); o != null; o = fa) {
o->fa == null ? rotate(o->c[1] == this) :
((f = o->c[1] == this) == (o->fa->c[1] == o)
? (o->rotate(f), rotate(f)) : (rotate(f), rotate(!f)));
}
maintain();
}
inline void expose(Node *p = null) {
splay();
if (c[1] != null)
c[1]->top = this, c[1]->fa = null;
(c[1] = p)->fa = this;
maintain();
}
inline Node *access() {
Node *x = this;
for (x->expose(); x->top; x = x->top)
x->top->expose(x);
return x;
}
inline void evert() {
access(), splay(), reverse();
}
inline void link(Node *f) {
Node *x = access();
x->reverse(), x->top = f;
}
inline void cut(Node *y) {
Node *x = this;
x->expose(), y->expose();
if (x->top == y) x->top = NULL;
if (y->top == x) y->top = NULL;
}
inline Node *findRoot() {
Node *f = this;
f->access(), f->splay();
while (f->pushDown(), f->c[0] != null) f = f->c[0];
return f;
}
inline void split(Node *v) {
v->evert(), access(), splay();
}
} pool[MAXN];
inline void init() {
null = pool, null->fa = null, null->size = 0;
}
inline void solve() {
register int n;
read(n);
init();
for (register int i = 1; i <= n + 1; i++) pool[i] = Node();
static int k[MAXN];
for (register int i = 1, tmp; i <= n; i++) {
read(k[i]);
(pool + i)->link(pool + std::min(i + k[i], n + 1));
}
register int q, p, x, y;
read(q);
for (register int i = 1; i <= q; i++) {
read(p);
if (p == 1) {
read(x), x++;
(pool + x)->split(pool + n + 1);
print((pool + x)->c[0]->size), print('\n');
} else {
read(x), read(y), x++;
(pool + x)->cut(pool + std::min(x + k[x], n + 1));
(pool + x)->link(pool + std::min(x + y, n + 1)), k[x] = y;
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
LinkCutTree::solve();
flush();
return 0;
}
分享到