水题笔记_ BZOJ4127 Abs [整体二分, 树链剖分, 清奇脑回路, 翻车]

代码神题…又写了一两周好像…

能胡出思路并不代表能得哪怕10分…

懵逼的 题目

****

扯淡的 题解

如果我把正数放在一边, 负数放在一边…

$0 \le d$ …也就是所有的点权都不会变小…

Emmmmm…我可以算出每一个点在什么时刻变成正数了…

然后就可以在树剖的时候在单点修改一波了吧…

$\uparrow$ 想的思路, 很简单吧…

尝试写一下就毁天灭地啦

想一想我需要什么…

  • 写一个普通树剖, 维护的是点权, 只需要一个树状数组be[]支持区间加, 单点查
    • 在普通树剖下加一个函数, 把一个修改操作拆成一些区间修改…vector<question> que[MAXN]
  • 写一个不普通树剖, 维护的是点权的绝对值, 线段树b要求可以区间加, 区间求和, 单点赋值
    • 这个区间加不是普通的区间加= =…节点还需要维护两个值: zz, fz: 表示区间内正/负数的个数(在单点赋值的时候顺便维护一下, 这个好像要用树状数组吧)
  • 写一个整体二分, 来找每一个数变成正数的时间(在哪一次操作后)NT[]
    • void ef(int leq, int riq, int lea, int ria):
      • leq == riq: NT[na[lea ~ ria].bh] = leq, return ;
      • midq = (leq + riq) >> 1, 把所有在midq时间点之前的修改操作都加上, 按照权值从大到小排序, 把大于零的挪到左边, 恢复他的权值, 小于零的挪到右边(结构体里需要一个变量ok判断是否权值大于0), 权值不变, 然后继续二分
  • 然后找答案的时候要在不普通树剖里做…

总复杂度是$\mathrm O(n \lg n)$

好像也没啥东西

然后就是花式翻车啦~

  • int i = re;

翻车$\times 1$

  • 差分, 区间修改, 把区间右端点修改为了zh (应该是-zh)

翻车$\times 2$

  • b[LS(dq)].lazy += x, b[RS(dq)].lazy += x$\to$b[LS(dq)].lazy = b[RS(dq)].lazy += x

翻车$\times 3$

  • ne = ... $\to$ n = ...

翻车$\times 4$

  • 两个修改都没有用LL做形参

翻车$\times 5$

沙茶的 代码

又是写了好几天的代码…

zky学长好毒啊

10k代码了解一下

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
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
/**************************************************************
Problem: 4127
User: Cansult
Language: C++
Result: Accepted
Time:15528 ms
Memory:33524 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define lowbit(i) ((i) & (-(i)))
#define LL long long
using namespace std;
struct tnode
{ int deep, fa, top, size, hs, begin, end; };
struct tedg
{ int from, to, next; };
struct question
{
int x, y, zh;
question() {}
question(int dqx, int dqy, int dqzh): x(dqx), y(dqy), zh(dqzh) {}
};
struct snode
{
int le, ri;
LL zh, lazy;
};
struct anode
{
int bh, ok;
LL zh;
};
struct bitt
{
LL b[MAXN];
int n;
void init(int xn)
{ n = xn; }
void txg(int wz, LL zh)
{
for (int i = wz; i <= n; i += lowbit(i))
b[i] += zh;
}
void xg(int le, int ri, LL zh)
{ txg(le, zh), txg(ri + 1, -zh); }
LL cx(int wz)
{
LL re = 0;
for (int i = wz; i; i -= lowbit(i))
re += b[i];
return re;
}
};
struct bitt2
{
int b[MAXN], n;
void init(int xn) { n = xn; }
void xg(int wz, int zh)
{
for (int i = wz; i <= n; i += lowbit(i))
b[i] += zh;
}
int cx(int le, int ri)
{
int re = 0;
for (int i = le - 1; i; i -= lowbit(i))
re -= b[i];
for (int i = ri; i; i -= lowbit(i))
re += b[i];
return re;
}
};
struct segt
{
int n;
snode b[MAXN << 2];
bitt2 fn;
void push_up(int dq)
{ b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh; }
void push_down(int dq)
{
LL& x = b[dq].lazy;
b[LS(dq)].lazy += x;
b[RS(dq)].lazy += x;
int ne = fn.cx(b[LS(dq)].le, b[LS(dq)].ri);
b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1 - ne) * x;
b[LS(dq)].zh -= x * ne;
ne = fn.cx(b[RS(dq)].le, b[RS(dq)].ri);
b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1 - ne) * x;
b[RS(dq)].zh -= x * ne;
x = 0;
}
void js(int dq, int le, int ri, int *a)
{
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].zh = abs(a[le]);
if (a[le] < 0)
fn.xg(le, 1);
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi, a);
js(RS(dq), mi + 1, ri, a);
push_up(dq);
}
void xgs(int dq, int le, int ri, LL zh) // 区间加
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].lazy += zh;
int ne = fn.cx(le, ri);
b[dq].zh += (ri - le + 1 - ne) * zh;
b[dq].zh -= ne * zh;
return ;
}
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xgs(RS(dq), le, ri, zh);
else if (ri <= mi)
xgs(LS(dq), le, ri, zh);
else
xgs(LS(dq), le, mi, zh), xgs(RS(dq), mi + 1, ri, zh);
push_up(dq);
}
void xgn(int dq, int wz, LL zh) // 单点赋值
{
if (b[dq].le == b[dq].ri)
{
b[dq].zh = zh;
fn.xg(wz, -1);
return ;
}
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz > mi)
xgn(RS(dq), wz, zh);
else
xgn(LS(dq), wz, zh);
push_up(dq);
}
LL cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
void init(int xn, int *a)
{
fn.init(n = xn);
js(1, 1, n, a);
}
};
struct tree
{
int a[MAXN], n, cnta, g[MAXN], cntb;
tedg tb[MAXN << 1];
tnode ta[MAXN];
segt b;
void adn(int from, int to)
{
tb[++cntb].next = g[from];
tb[cntb].from = from;
tb[cntb].to = to;
g[from] = cntb;
}
void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].size = 1;
for (int i = g[dq]; i; i = tb[i].next)
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, deep + 1);
ta[dq].size += ta[tb[i].to].size;
if (ta[tb[i].to].size > ta[ta[dq].hs].size)
ta[dq].hs = tb[i].to;
}
}
void dfs(int dq, int *xa)
{
a[ta[dq].begin = ++cnta] = xa[dq];
if (ta[dq].hs)
ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs, xa);
for (int i = g[dq]; i; i = tb[i].next)
if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to, xa);
}
ta[dq].end = cnta;
}
LL cx(int x, int y)
{
LL re = 0;
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
re += b.cx(1, ta[ta[x].top].begin, ta[x].begin);
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
re += b.cx(1, ta[x].begin, ta[y].begin);
return re;
}
void QwQ(int x, int y, vector<question>& dqq, int zh) // 分解询问
{
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
dqq.push_back(question(ta[ta[x].top].begin, ta[x].begin, zh));
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
dqq.push_back(question(ta[x].begin, ta[y].begin, zh));
}
void QAQ(int xn, int *xa) // 初始化
{
n = xn;
ta[1].top = ta[1].fa = 1;
init(1, 1);
dfs(1, xa);
b.init(n, a);
}
}TA;
int q, n, xgq, cxq;
LL bz[MAXN];
anode a[MAXN], tmp[MAXN];
bitt b;
question cx[MAXN];
vector<question> que[MAXN];
vector<int> tim[MAXN];
bool cmp(anode x, anode y)
{ return x.ok > y.ok; }
bool cmpz(anode x, anode y)
{ return x.zh < y.zh; }
void ef(int leq, int riq, int lea, int ria)
{
if (lea > ria)
return ;
if (leq == riq)
{
for (int i = 0; i < que[leq].size(); i++)
b.xg(que[leq][i].x, que[leq][i].y, que[leq][i].zh);
for (int i = lea; i <= ria; i++)
{
LL dqc = b.cx(TA.ta[a[i].bh].begin);
if (a[i].zh + dqc >= 0)
tim[leq].push_back(a[i].bh), bz[a[i].bh] = a[i].zh + dqc;
}
for (int i = 0; i < que[leq].size(); i++)
b.xg(que[leq][i].x, que[leq][i].y, -que[leq][i].zh);
return ;
}
int mi = (leq + riq) >> 1;
for (int i = leq; i <= mi; i++)
for (int j = 0; j < que[i].size(); j++)
b.xg(que[i][j].x, que[i][j].y, que[i][j].zh);
int nria = lea - 1;
for (int i = lea; i <= ria; i++)
{
a[i].ok = 0;
LL dqc = b.cx(TA.ta[a[i].bh].begin);
if (a[i].zh + dqc > 0)
++nria, a[i].ok = 1;
else
a[i].zh += dqc;
}
for (int i = leq; i <= mi; i++)
for (int j = 0; j < que[i].size(); j++)
b.xg(que[i][j].x, que[i][j].y, -que[i][j].zh);
sort(a + lea, a + ria + 1, cmp);
ef(leq, mi, lea, nria);
ef(mi + 1, riq, nria + 1, ria);
}
int main()
{
int sra[MAXN];
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i].zh), sra[i] = a[i].zh, a[i].bh = i;
for (int i = 1, srx, sry; i < n; i++)
{
scanf("%d%d", &srx, &sry);
TA.adn(srx, sry);
TA.adn(sry, srx);
}
TA.QAQ(n, sra);
for (int i = 1, sre, srx, sry, srz; i <= q; i++)
{
scanf("%d", &sre);
if (sre == 1)
{
++xgq;
scanf("%d%d%d", &srx, &sry, &srz);
TA.QwQ(srx, sry, que[xgq], srz);
}
else
{
++cxq;
scanf("%d%d", &cx[cxq].x, &cx[cxq].y);
cx[cxq].zh = xgq;
}
}
sort(a + 1, a + n + 1, cmpz);
int zn = 0;
a[n + 1].zh = 1;
for (int i = 1; i <= n + 1; i++)
if (a[i].zh >= 0)
{
zn = i - 1;
break;
}
b.init(n);
if (xgq)
ef(1, xgq, 1, zn);
for (int i = 0, cxi = 1; i <= xgq; i++)
{
for (int j = 0; j < que[i].size(); j++)
TA.b.xgs(1, que[i][j].x, que[i][j].y, que[i][j].zh);
for (int j = 0; j < tim[i].size(); j++)
{
int wz = TA.ta[tim[i][j]].begin;
TA.b.xgn(1, wz, bz[tim[i][j]]);
}
while (cxi <= cxq && cx[cxi].zh == i)
printf("%lld\n", TA.cx(cx[cxi].x, cx[cxi].y)), ++cxi;
}
return 0;
}
/*
6 3
6 0 -6 2 0 5
1 4
1 2
1 5
2 6
6 3
1 2 3 3
1 6 6 6
2 4 4
*/

By 沙茶 Cansult