「SCOI2015」「BZOJ-4448」情报传递-Link-Cut-Tree

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名(可能没有)下线,除 $1$ 名大头目外其余 $n - 1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严,每名情报员只能与自己的上,下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

  1. 搜集情报:指派 $T$ 号情报员搜集情报
  2. 传递情报:将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员

情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为0;-旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加1点危险值(开始搜集情报的当天危险值仍为0,第2天危险值为1,第3天危险值为2,以此类推)。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全,每条情报都有一个风险控制值C。余特公司认为,参与传递这条情报的所有情报员中,危险值大于C的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

链接

BZOJ-4448

题解

为什么网上全是链剖+主席树呢?

我们考虑离线,不就是 LCT 板题吗?

考虑到对于每个查询操作,只有距离它 $C + 1$ 天之前的修改操作对它有贡献,所以可以将操作离线,保证每次修改后直接处理查询即可。

代码

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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
/*
* created by xehoth on 01-04-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 val, sum, size;
Node() : top(NULL), rev(false), fa(null), val(0), sum(0), size(1) {
c[0] = c[1] = null;
}
inline void reverse() {
rev ^= 1, std::swap(c[0], c[1]);
}
inline void maintain() {
sum = val + c[0]->sum + c[1]->sum, size = 1 + c[0]->size + c[1]->size;
}
inline bool relation() {
return this == fa->c[1];
}
inline void pushDown() {
rev ? c[0]->reverse(), c[1]->reverse(), rev = false : 0;
}
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(const int n) {
null = pool, null->fa = null, null->size = 0;
for (register int i = 1; i <= n; i++) pool[i] = Node();
}
inline void link(const int u, const int v) {
(pool + u)->link(pool + v);
}
inline void cut(const int u, const int v) {
(pool + u)->cut(pool + v);
}
inline void update(const int u, const int val) {
(pool + u)->splay();
(pool + u)->val = val;
(pool + u)->maintain();
}
inline void query(const int u, const int v, int &size, int &sum) {
(pool + v)->split(pool + u);
sum = (pool + v)->sum, size = (pool + v)->size;
}
struct Day {
int id, task;
int u, v, c;
struct Answer {
int size, sum;
} ans;
inline bool operator<(const Day &other) const {
if (c == other.c) return task < other.task;
return c < other.c;
}
} days[MAXN];
inline bool compareByC(const Day &a, const Day &b) {
if (a.c == b.c) return a.task < b.task;
else return a.c < b.c;
}
inline bool compareByID(const Day &a, const Day &b) {
return a.id < b.id;
}
inline void solve() {
register int n, m;
read(n);
init(n);
for (register int i = 1, u; i <= n; i++) {
read(u);
if (u != 0) link(u, i);
}
read(m);
register bool flag1 = true, flag2 = true;
for (register int i = 0; i < m; i++) {
days[i].id = i, read(days[i].task);
if (days[i].task == 2) {
read(days[i].u), days[i].c = i;
} else {
register int tmp;
read(days[i].u), read(days[i].v), read(tmp);
days[i].c = i - tmp;
}
}
std::sort(days, days + m, &compareByC);
for (register int i = 0; i < m; i++) {
if (days[i].task == 2) {
update(days[i].u, 1);
} else {
query(days[i].u, days[i].v, days[i].ans.size, days[i].ans.sum);
}
}
std::sort(days, days + m, &compareByID);
for (register int i = 0; i < m; i++) {
if (days[i].task == 1) print(days[i].ans.size), print(' '),
print(days[i].ans.sum), print('\n');
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
LinkCutTree::solve();
flush();
return 0;
}
分享到