翻车笔记_ [Hnoi2016] 网络 [树链剖分, 翻车, 清奇脑回路]

…菜到一定程度了…

我怎么这么菜…

HN大爷都太神了 Orzz

懵逼的 题目

点击确认: Cansult太菜了

扯淡的 题解

一开始看错题了…看成是出错的服务器能影响到的路径最大值了…

Emmm…区间修改, 区间撤回, 单点取$\max$…

标记永久化啊…把标记设成一个堆, 然后再搞一个set记录哪些标记被撤回过好咯

然后看了看ljh_2000大佬的blog, 学习了一个写法, 感觉比较资瓷啊:

每一个线段树搞两个大根堆, 一个表示修改的标记, 一个表示撤回的标记

如果两个堆顶的元素相同, 就把两个堆都弹出, 这样就可以维护带撤回的最大值了

然后写写写…艹我又双叒叕看错题了…

Emmm…不受影响的…那我查询剩下的部分就好了嘛 ←沙茶

然后重写了一个区间查询的版本…

…等等…不对劲啊…

Emmmmmmm…那咋搞啊…

啊! 直接修改路径的补集不就可以了嘛! 怎么修改路径的补集啊…

啊! 我把整棵树都赋成要修改的值, 然后在链上撤回不就好了嘛!

写写写…

等等…你都标记永久化了…怎么在子区间撤回啊…

然后看题解

哦…我真傻, 真的

把树链剖分每次跳的两个端点记录下来

然后按照端点排序, 把两个区间之间的部分修改了就好了

沙茶的 代码

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
/**************************************************************
Problem: 4538
User: Cansult
Language: C++
Result: Accepted
Time:10816 ms
Memory:73352 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define MAXN (100000 + 5)
#define MAXQ (200000 + 5)
#define pii pair<int, int>
const int root = 1;
using namespace std;
struct tnode
{
int deep, fa, top, hs, size, begin, end;
}ta[MAXN];
int cnta, n;
struct que
{
int x, y, z;
}sr[MAXQ];
struct edg
{
int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntt = -1;
struct cmp
{
bool operator () (const int x, const int y)
{ return x < y; }
};
struct node
{
int le, ri;
priority_queue<int, vector<int>, cmp> qwq[2];
}b[MAXN << 2];
pii a[MAXN];
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].qwq[0].push(-1);
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh, int e)
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].qwq[e].push(zh);
while (!b[dq].qwq[0].empty() && !b[dq].qwq[1].empty() && b[dq].qwq[0].top() == b[dq].qwq[1].top())
b[dq].qwq[0].pop(), b[dq].qwq[1].pop();
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg(RS(dq), le, ri, zh, e);
else if (ri <= mi)
xg(LS(dq), le, ri, zh, e);
else
xg(LS(dq), le, mi, zh, e), xg(RS(dq), mi + 1, ri, zh, e);
}
int cx(int dq, int wz)
{
int re = b[dq].qwq[0].top();
if (b[dq].le == b[dq].ri)
return re;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz > mi)
return max(re, cx(RS(dq), wz));
else
return max(re, cx(LS(dq), wz));
}
void adn(int from, int to)
{
tb[++cntt].next = tg[from];
tb[cntt].from = from;
tb[cntt].to = to;
tg[from] = cntt;
}
void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].size = 1;
for (int i = tg[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)
{
ta[dq].begin = ++cnta;
if (ta[dq].hs)
ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
for (int i = tg[dq]; ~i; i = tb[i].next)
if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
ta[tb[i].to].top = tb[i].to, dfs(tb[i].to);
ta[dq].end = cnta;
}
void solve(int x, int y, int zh, int e)
{
/*puts("\n------------");
printf("x: %d\ty: %d\tzh: %d\te: %d\n", x, y, zh, e);*/

int cnt = 0;
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
a[++cnt] = make_pair(ta[ta[x].top].begin, ta[x].begin);
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
a[++cnt] = make_pair(ta[x].begin, ta[y].begin);
sort(a + 1, a + cnt + 1);

/*for (int i = 1; i <= cnt; i++)
printf("%d\t%d\n", a[i].first, a[i].second);
puts("----------------------");*/

if (a[1].first > 1)
xg(1, 1, a[1].first - 1, zh, e);
if (a[cnt].second < n)
xg(1, a[cnt].second + 1, n, zh, e);
for (int i = 2; i <= cnt; i++)
if (a[i - 1].second + 1 <= a[i].first - 1)
xg(1, a[i - 1].second + 1, a[i].first - 1, zh, e);
}
int main()
{
memset(tg, -1, sizeof(tg));
int q;
scanf("%d%d", &n, &q);
for (int i = 1, srx, sry; i < n; i++)
scanf("%d%d", &srx, &sry), adn(srx, sry), adn(sry, srx);
ta[root].top = ta[root].fa = root;
init(root, 1);
dfs(root);
js(1, 1, n);
for (int i = 1, sre, srx; i <= q; i++)
{
scanf("%d", &sre);
if(sre == 0)
scanf("%d%d%d", &sr[i].x, &sr[i].y, &sr[i].z), solve(sr[i].x, sr[i].y, sr[i].z, 0);
else if (sre == 1)
scanf("%d", &srx), solve(sr[srx].x, sr[srx].y, sr[srx].z, 1);
else if (sre == 2)
scanf("%d", &srx), printf("%d\n", cx(1, ta[srx].begin));
}
return 0;
}

/*
13 23
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
6 11
7 12
7 13
2 1
0 8 13 3
0 9 12 5
2 9
2 8
2 2
0 10 12 1
2 2
1 3
2 7
2 1
0 9 5 6
2 4
2 5
1 7
0 9 12 4
0 10 5 7
2 1
2 4
2 12
1 2
2 5
2 3
*/

By 超级无敌大sb Cansult