目录

  1. 引言
  2. BZOJ 3159: 决战
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. Source
    8. 题目分析
    9. 代码

引言

BZOJ 3159: 决战 题解

BZOJ 3159: 决战

  • Time Limit: 10 Sec

  • Memory Limit: 512 MB

Description

Input

第一行有三个整数N、M和R,分别表示树的节点数、指令和询问总数,以及X国的据点。

接下来N-1行,每行两个整数X和Y,表示Katharon国的一条道路。

接下来M行,每行描述一个指令或询问,格式见题目描述。

Output

对于每个询问操作,输出所求的值。

Sample Input

5 8 1

1 2

2 3

3 4

4 5

Sum 2 4

Increase 3 5 3

Minor 1 4

Sum 4 5

Invert 1 3

Major 1 2

Increase 1 5 2

Sum 1 5

Sample Output

0

0

6

3

19

HINT

1<=N,M<=50000.且对于运送操作1<=W<=1000

Source

Katharon+#1

题目分析

很好的动态树技巧……

最近写了几发JCY课件上的题,感觉都巨强无比……应该是我太菜了,每道题都差不多写半(half)天

这道题也是如此,我们发现,前几个操作都是动态树的ZZ操作对吧,但是最后一个要我们资磁值的翻转,这就有点为难了,因为我们如果直接在LCT上翻转的话,实际上相当于什么都没有做对吧……

但如果顺着这个方向想,我们可以发现,之所以在原来的LCT上不能直接翻转,是因为它上面的值和点是对应的,我们翻转只是改变了树的形态,而点与值的对应关系并没有发生改变,而题目的要求,使得我们必须改变这种对应关系,所以,我们可以先考虑在一棵Splay中翻转对应关系,但是这个并不好维护,为什么呢?因为这种翻转是和其他的子树相关联的,比如我现在要在左子树里面查找一个值,而这个值很显然也和其他某个子树有关(如果当前树的值被翻转了),这样这种关系就会过于复杂以至于根本无法维护

那么还可以怎么办呢?我们发现,主要矛盾就在于点与值的捆绑维护,那么我们把它们拆开,分别来维护,不就能够解决这样的问题了吗?

所以,我们考虑构建两棵LCT,一棵维护结构,而另一棵维护值,注意,此时两棵LCT相同编号的点不一定是对应点,我们不妨称前者为TrueLCT,后者为ValueLCT

我们在执行其他修改操作以及询问操作的时候,我们直接在两棵LCT上同步进行,而在值翻转的时候,我们只翻转ValueLCT上的点

而如何实现同步进行呢?我们知道,为了保证每次操作都能够同步,我们必须保证两棵LCT的每个Splay能够两两对应,而且对应的这两个Splay点数必须相同(内部具体结构不必完全相同),进一步,我们可以知道,这两个对应的Splay,就分别维护了某一特定链的形态和值,也即链上深度排名为$i$的点$x$,在TrueLCT中的对应的点编号就是$x$,而在ValueLCT里面对应的点是它在TrueLCT里面所在Splay对应的ValueLCT里面的Splay的排名为$i$的那个点(好好理解一下~),这样,我们就可以快速的找到一个点的值是多少,而且,通过在两棵LCT上同步进行Split操作,我们也就可以回答链的询问(因为这条链对应的那两棵Splay形态肯定是一致的),所以这种对应是有很大的意义的

我们发现,此时由于两个编号相同的点不一定关联,所以我们首先要在TrueLCT的每棵Splay的根上维护这个根在ValueLCT里面的对应Splay上的某个点(不一定就是根的对应点,只是为了定位所在的Splay,为了方便不妨称为定位点),这样才能够知道每个点的对应点在ValueLCT里面的哪棵Splay上,才能够进行找对应点的操作,而且,定位点信息当且仅当当前这个点是所在Splay的根的时候才有意义

注意,由于ValueLCT服务于TrueLCT,且受TrueLCT支配,所以它的具体形态无关紧要,它上面的Splay之间的具体形态信息可能是错误的,但是这样不会导致问题,因为我们在进行操作时,不会根据ValueLCT的形态来进行操作,而是根据TrueLCT的形态以及实际需要来查找或更新ValueLCT里面的对应Splay的信息,所以ValueLCT里面的具体形态无关紧要

说起来大概就是这么多,下面是每个具体的操作方(xi)法(jie)(其实都是我入的坑……):

  • 找对应点操作,假设我们要找$x$(在TrueLCT中)的对应点$x’$(在ValueLCT中),我们首先把$x$Splay到根,然后可以直接得到它在Splay中的排名$k$,然后,我们在ValueLCT中把之前提到的定位点Splay到根,然后通过排名$k$在它的子树里面寻找排名为$k$的点即可,最后,为了方便及正确性,我们把$x$的定位点更新为刚找到的它的对应点

  • access操作,我们可以发现,在这个操作里面我们干的无非就是两件事,一是合并Splay,二是分裂Splay,为了方便我们直接把这两个操作放在一起。假设当前以$x$为根的Splay要合并到$y$点上,$y$要与某个点$z$断开,那么,我们为了同步维护两个LCT里面的Splay形态,我们首先需要找到$x$的对应点$x’$,然后,我们同时断开$x$和$x’$的右儿子与它们各自的连接并连接到新点上即可(把它们的右儿子更新为需要的那个点),注意,由于在TrueLCT中,$x$的右儿子原先不是根,现在成为了新根,为了正确性,我们要更新它的定位点信息为$x’$原来的右儿子,同时,因为ValueLCT上的形态不保证正确,所以,$x’$新接上去的点的父亲不一定是$x’$,我们需要强制地把新连上去的点的父亲更新为$x’$,这个操作里面就是这两个细节

  • pushdown操作,由于我们现在要维护的信息是需要随时查询的,所以我们不能延迟信息更新,也就是说,在得到标记的那一刻就要更新自己维护的信息,而不是等到下传标记时才更新自己的信息,但是反转标记除外,因为它影响的范围是自己的下一层,在查询到下一层时当前点的标记显然已经下传完毕了,所以就不会有什么影响,注意,我们在TureLCT上维护的标记只有反转标记,信息只有左右儿子,父亲,子树大小以及定位点,剩下的都交给ValueLCT维护

  • rotate操作(只限于TrueLCT),我们为了保证定位点信息的正确性,需要在rotate时更新,比如现在已知单/双旋一次之后这个点就会成为根,那么我们就需要把根的定位点信息传给这个点,在ValueLCT里面就无所谓了

  • splay操作,其实由于没有严格限制,所以无所谓,但是为了严密性,我们最好同时对两棵LCT中的点进行Splay,也就是说,在对一个点进行Splay以后(TrueLCT中),最好把它的对应点(ValueLCT中)也Splay一下,这样处理较为方便

  • moveroot, split以及修改查询等操作,正常做就可以了,注意修改查询要保证当前的点(ValueLCT中)为所在Splay的根,这也就是为什么上面的Splay操作最好那样写

其实全都是TMD细节,就这一道题,先是写了一份一千多行的代码,结果因为没维护定位点所以错了(我本以为可以不维护这东西)……后来重新写了一份三百多行的,又调了大半天……才TMD过

代码

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
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define maxn 100005
#define ls ch[x][0]
#define rs ch[x][1]
#define _ls ch[_x][0]
#define _rs ch[_x][1]
#define ll long long int
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') ch = gc(), f = 0;
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
namespace TrueLCT{
int fa[maxn];
int ch[maxn][2];
bool rev[maxn];
int poi[maxn];//只有Splay树根上的才有意义
int siz[maxn];
inline bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
siz[x] = siz[ls] + siz[rs] + 1;
}
inline void pass(int x, bool r){
rev[x] ^= r; if (r) swap(ls, rs);
}
inline void pushdown(int x){
if (ls) pass(ls, rev[x]);
if (rs) pass(rs, rev[x]);
rev[x] = 0;
}
inline void rotate(int x){
int k = x;
x = fa[x];
int d = ch[x][1] == k;
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
int st[maxn];
int cst = 0;
void splay(int x){
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if (is_root(f2)) poi[x] = poi[f2];
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
rotate(x);
}
else rotate(x), poi[x] = poi[f1];
}
}
}
using TrueLCT :: poi;
using TrueLCT :: pass;
namespace ValueLCT{
int mx[maxn];
int mi[maxn];
int val[maxn];
int add[maxn];
ll sum[maxn];
int fa[maxn];
int ch[maxn][2];
bool rev[maxn];
int siz[maxn];
inline bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
siz[x] = siz[ls] + siz[rs] + 1;
sum[x] = sum[ls] + sum[rs] + val[x];
mx[x] = max(val[x], max(mx[ls], mx[rs]));
mi[x] = val[x];
if (ls) mi[x] = min(mi[x], mi[ls]);
if (rs) mi[x] = min(mi[x], mi[rs]);
}
inline void pass(int x, int k, bool r){
mx[x] += k, mi[x] += k, val[x] += k, sum[x] += (ll)siz[x] * k, add[x] += k;
rev[x] ^= r; if (r) swap(ls, rs);
}
inline void pushdown(int x){
if (ls) pass(ls, add[x], rev[x]);
if (rs) pass(rs, add[x], rev[x]);
add[x] = rev[x] = 0;
}
inline void rotate(int x){
int k = x;
x = fa[x];
int d = ch[x][1] == k;
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
int st[maxn];
int cst = 0;
void splay(int x){
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
rotate(x);
}
}
int find_by_rank(int rank, int x){
splay(x);
while (x){
pushdown(x);
int left = (ls) ? siz[ls] : 0;
if (rank <= left) x = ls;
else if (rank == left + 1) return x;
else rank -= left + 1, x = rs;
}
return -1;
}
}
using ValueLCT :: add;
using ValueLCT :: mi;
using ValueLCT :: mx;
using ValueLCT :: sum;
using ValueLCT :: pass;
int get_value_point(int x){
int _x = ValueLCT :: find_by_rank(TrueLCT :: siz[TrueLCT :: ls] + 1, poi[x]);
poi[x] = _x;
return _x;
}
void access(int x){
int t = 0;
int _t = 0;
while (x){
TrueLCT :: splay(x);
int _x = get_value_point(x);
ValueLCT :: splay(_x);
poi[TrueLCT :: rs] = ValueLCT :: _rs;
TrueLCT :: rs = t;
ValueLCT :: _rs = _t;
ValueLCT :: fa[_t] = _x;
TrueLCT :: pushup(x);
ValueLCT :: pushup(_x);
t = x;
_t = _x;
x = TrueLCT :: fa[x];
}
}
int splay(int x){
TrueLCT :: splay(x);
int _x = get_value_point(x);
ValueLCT :: splay(_x);
return _x;
}
int moveroot(int x){
access(x);
int _x = splay(x);
pass(x, 1);
pass(_x, 0, 1);
return _x;
}
int split(int x, int y){
moveroot(y);
access(x);
int _x = splay(x);
return _x;
}
void link(int x, int y){
int _x = moveroot(x);
TrueLCT :: fa[x] = y;
ValueLCT :: fa[_x] = poi[y];
}
void Add(int x, int y, int z){
int _x = split(x, y);
pass(_x, z, 0);
}
void flip(int x, int y){
int _x = split(x, y);
pass(_x, 0, 1);
}
void get_mx(int x, int y){
int _x = split(x, y);
printf("%d\n", mx[_x]);
}
void get_mi(int x, int y){
int _x = split(x, y);
printf("%d\n", mi[_x]);
}
void get_sum(int x, int y){
int _x = split(x, y);
printf("%lld\n", sum[_x]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("war.in", "r", stdin);
#endif
int x, y, z;
read(n), read(m), read(x);
rep(i, 1, n) poi[i] = i;
rep(i, 1, n - 1) read(x), read(y), link(x, y);
rep(i, 1, m){
char op = gc();
while (op != 'M' && op != 'S' && op != 'I') op = gc();
switch(op){
case 'I': {
op = gc(), op = gc();
read(x), read(y);
if (op == 'c') read(z), Add(x, y, z);
else if (op == 'v') flip(x, y);
else assert(false);
break;
}
case 'S': read(x), read(y), get_sum(x, y); break;
case 'M': {
op = gc();
read(x), read(y);
if (op == 'a') get_mx(x, y);
else if (op == 'i') get_mi(x, y);
else assert(false);
break;
}
default: assert(false);
}
}
return 0;
}

namespace和assert大法好啊!!!