水题笔记_ 18-3-1测试 [线段树, 网络流, 树链剖分]

依旧是水的一匹的考试…三道原题…两道写过…

T1

begin: 7:30
裸网络流…啥都没改差评
码了30min+-好菜啊QAQ明明是个小模板…

T2

又是原题调了好久…_(:з」∠)_我凉了啊QAQ
写了1h终于过样例了…明明当初做的时候是1A啊QAQ

T3

9:00…
woc这个题太™恶心了…虽然一眼就是个线段树裸题…但是…太恶心了…写main函数我就写了108行…加上我的垃圾字符串…凉凉….
10:00Maya我终于写完main函数辣QAQ! 一看时间觉得非常不稳啊赶紧码码码…
30min线段树写完了…
诶怎么错了啊QAQ
原先好像写过一发线段树就是这种区间覆盖的…然后标记太乱就一直WA…现在也还晾在那…
调试…mdpush_down的时候区间覆盖完了就应该把区间翻转去掉…就这样调了1h….凉凉
不管怎样收卷前调出样例了hin开心…

事后…

Maya我的调试忘改了…为了调试方便我数组就开了…5…然后T3就凉了…挂成10分样例分…md$n^2$暴力都比我强…
然后改过来发现崩溃了…一看数据md怎么有这种数据…

1
2
3
4
S [3,5]
S [3,5]
U [5,5)
U (5,5)

woc你家区间这么写mmp…特判了一下

1
2
if (le > ri)
return ;

然后还是WAWAWA…手动输了数据全™对了??? 交到b站也A了??? 似乎是Cena的锅…

癌…因为CTL的集合书写和没删调试痛失AK机会…QAQ

代码 && 简单介绍

T1

有必要说嘛?

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define LINF (0x7ffffffffll)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define RS(dq) (((dq) << 1) | 1)
#define LS(dq) ((dq) << 1)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define LL long long
using namespace std; // 答案需要使用ll
struct edg
{
int from, to, next, cap, flow;
edg() {}
edg(int fr, int t, int ne, int ca, int fl): from(fr), to(t), next(ne), cap(ca), flow(fl) {}
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN], s, t;
LL ans;
inline void adn(int, int, int);
LL dinic(int, LL);
int bfs();
void solve();
int main()
{
//#define Debug
#ifndef Debug
freopen("ditch.in" ,"r", stdin);
freopen("ditch.out", "w", stdout);
#endif
int m, n;
scanf("%d%d", &m, &n);
s = 1, t = n;
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
adn(sry, srx, 0);
}
solve();
printf("%lld", ans);
return 0;
}
inline void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap, 0);
g[from] = cntb;
}
LL dinic(int dq, LL maxf)
{
if (dq == t || (!maxf))
return maxf;
LL re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if ((dis[b[i].to] == dis[dq] + 1) && b[i].cap > b[i].flow)
{
LL zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
re += zl;
maxf -= zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}
int bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if ((!dis[b[i].to]) && b[i].cap > b[i].flow)
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
void solve()
{
while (bfs())
ans += dinic(s, LINF);
}

/*
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
*/

T2

裸的树链剖分…考模板×原题是要干甚啊…

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXQ (100000 + 5)
#define MNULL (MAXN - 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define RS(dq) (((dq) << 1) | 1)
#define LS(dq) ((dq) << 1)
#define rev(i) ((((i) - 1) ^ 1) + 1)
const int root = 0;
using namespace std;
struct edg
{
int from, to, next;
edg() {}
edg(int fr, int t, int ne): from(fr), to(t), next(ne) {}
} tb[MAXN << 1];
int tg[MAXN], cntb;
struct tnode
{
int fa, hs, sum, top, begin, end, deep;
} ta[MAXN];
struct node
{
int le, ri, zh, lazy;
} b[MAXN << 3];
int n, a[MAXN], cnta;
void js(int, int, int); //
void xg(int, int, int, int); //
int cx(int, int, int); //
inline void push_up(int);
inline void push_down(int);
inline void adn(int, int); //
void init(int, int); //
void dfs(int); //
int solve(int);
int main()
{
//#define Debug
#ifndef Debug
freopen("manager.in" ,"r", stdin);
freopen("manager.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int srx;
scanf("%d", &srx);
adn(srx, i);
}
ta[root].fa = root, ta[root].top = root;
init(root, 1);
dfs(root);
js(1, 1, n);
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
char sre[20 + 5];
int srx;
scanf("%s%d", sre, &srx);
if (sre[0] == 'u')
{
printf("%d\n", cx(1, ta[srx].begin, ta[srx].end));
xg(1, ta[srx].begin, ta[srx].end, 0);
}
else
printf("%d\n", ta[srx].deep - solve(srx));
}
return 0;
}
inline void adn(int from, int to)
{
tb[++cntb] = edg(from, to, tg[from]);
tg[from] = cntb;
}
void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].sum = 1;
ta[dq].hs = MNULL;
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);
if (ta[ta[dq].hs].sum < ta[tb[i].to].sum)
ta[dq].hs = tb[i].to;
ta[dq].sum += ta[tb[i].to].sum;
}
}
}
/*
struct tnode
{
int fa, hs, sum, top, begin, end, deep;
} ta[MAXN];
*/
void dfs(int dq)
{
ta[dq].begin = ++cnta;
if (ta[dq].hs != MNULL)
{
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 js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].lazy = 2;
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)
{
if(b[dq].lazy != 2)
push_down(dq);
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].lazy = zh;
b[dq].zh = (ri - le + 1) * zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg(RS(dq), le, ri, zh);
else if (ri <= mi)
xg(LS(dq), le, ri, zh);
else
xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
push_up(dq);
}
int cx(int dq, int le, int ri)
{
if (b[dq].lazy != 2)
push_down(dq);
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
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);
}
inline void push_up(int dq)
{ b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh; }
inline void push_down(int dq)
{
int x;
b[LS(dq)].lazy = b[RS(dq)].lazy = x =b[dq].lazy;
b[LS(dq)].zh = (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
b[RS(dq)].zh = (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
b[dq].lazy = 2;
}
int solve(int x)
{
int re = 0;
while (ta[x].top != root)
{
re += cx(1, ta[ta[x].top].begin, ta[x].begin);
xg(1, ta[ta[x].top].begin, ta[x].begin, 1);
x = ta[ta[x].top].fa;
}
re += cx(1, ta[ta[x].top].begin, ta[x].begin);
xg(1, ta[ta[x].top].begin, ta[x].begin, 1);
return re;
}

/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/

T3

把每个数分成两个点, 一个是数本身, 一个是这个数和他右边那个数之间的开区间
即:
开闭区间的实现方法

然后集合间计算的实现可以看注释

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#define MAXN (80000 + 1)
#define MAXQ (70000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define wz(x) (((x) << 1) + 2)
#define ln(x) (((x) << 1) + 1)
#define rn(x) (((x) << 1) + 3)
#define swap(a, b) {int t = a; a = b; b = t;}
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct node
{
int zh1, zh0, le, ri;
int lazy01;
bool lazyf;
} b[MAXN << 5];
// 每个数要拆成两个来确定开闭区间
// U: 修改给定区间为1
// I: 修改非给定区间为0
// D: 修改给定区间为0
// C: 修改非给定区间为0, 给定区间内取反
// S: 给定区间取反
void js(int, int, int);
void xg(int, int, int, int);
// 0: ->0
// 1: ->1
// 2: 0->1, 1->0
int cx(int, int);
void push_down(int);
void push_up(int);
void sti(string&, int&, int&);
int main()
{
//#define Debug
#ifndef Debug
freopen("interval.in" ,"r", stdin);
freopen("interval.out", "w", stdout);
#endif
js(1, 1, (MAXN << 2));
string sre, sr;
while (cin >> sre)
{
cin >> sr;
bool zb = (sr[0] == '['), yb = (sr[sr.length() - 1] == ']');
int lex, rix;
sti(sr, lex, rix);
int dql = (zb ? wz(lex) : rn(lex)), dqr = (yb ? wz(rix) : ln(rix));
if (sre == "U")
xg(1, dql, dqr, 1);
if (sre == "D")
xg(1, dql, dqr, 0);
if (sre == "C" || sre == "S")
xg(1, dql, dqr, 2);
if (sre == "I" || sre == "C")
{
dql = (zb ? rn(lex - 1) : wz(lex)), dqr = (yb ? ln(rix + 1) : wz(rix));
if (dql > 0)
xg(1, 1, dql, 0);
if (dqr < (MAXN << 2))
xg(1, dqr, (MAXN << 2) - 1, 0);
}
}
bool ok = false;
vector<pii> ans; // 1: self, 2: right
for (int i = 0; i < MAXN; i++)
{
if (cx(1, wz(i)))
ans.push_back(mkp(i, 1)), ok = true;
if (cx(1, rn(i)))
ans.push_back(mkp(i, 2)), ok = true;
}
if (!ok)
{
puts("empty set");
return 0;
}
int n = ans.size();
bool last = false;
for (int i = 0; i < n; i++)
{
if (ans[i].second == 1)
{
if (!last)
cout << "[" << ans[i].first << ",", last = true;
if (i == n - 1 || ans[i + 1].first != ans[i].first)
cout << ans[i].first << "] ", last = false;
}
else if (ans[i].second== 2)
{
if (!last)
cout << "(" << ans[i].first << ",", last = true;
if (i == n - 1 || (ans[i + 1].second != 1 || ans[i + 1].first != ans[i].first + 1))
cout << ans[i].first + 1 << ") ", last = false;
}
}
return 0;
}
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].lazy01 = 2, b[dq].lazyf = false;
if (le == ri)
{
b[dq].zh0 = 1;
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
push_up(dq);
}
// 0: ->0
// 1: ->1
// 2: 0->1, 1->0
void xg(int dq, int le, int ri, int zh)
{
if (le > ri)
return ;
if (b[dq].lazy01 != 2 || b[dq].lazyf)
push_down(dq);
if (b[dq].le == le && b[dq].ri == ri)
{
if (zh < 2)
{
b[dq].lazy01 = zh;
b[dq].zh1 = (b[dq].ri - b[dq].le + 1) * zh;
b[dq].zh0 = (b[dq].ri - b[dq].le + 1) - b[dq].zh1;
}
else
{
b[dq].lazyf = !b[dq].lazyf;
swap(b[dq].zh0, b[dq].zh1);
}
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
xg(LS(dq), le, ri, zh);
else if (le > mi)
xg(RS(dq), le, ri, zh);
else
xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
push_up(dq);
}
int cx(int dq, int wz)
{
if (b[dq].lazy01 != 2 || b[dq].lazyf)
push_down(dq);
if (b[dq].le == b[dq].ri && b[dq].le == wz)
return b[dq].zh1;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
return cx(LS(dq), wz);
else
return cx(RS(dq), wz);
}
void sti(string& s, int& le, int& ri)
{
int wz = 1;
le = ri = 0;
while (s[wz] != ',')
le = (le << 1) + (le << 3) + s[wz++] - '0';
++wz;
while (s[wz] <= '9' && s[wz] >= '0')
ri = (ri << 1) + (ri << 3) + s[wz++] - '0';
}
void push_up(int dq)
{
b[dq].zh0 = b[LS(dq)].zh0 + b[RS(dq)].zh0;
b[dq].zh1 = b[LS(dq)].zh1 + b[RS(dq)].zh1;
}
void push_down(int dq)
{
if (b[dq].lazy01 != 2)
{
int x;
b[RS(dq)].lazy01 = b[LS(dq)].lazy01 = x = b[dq].lazy01;
b[RS(dq)].zh1 = x * (b[RS(dq)].ri - b[RS(dq)].le + 1);
b[RS(dq)].zh0 = (b[RS(dq)].ri - b[RS(dq)].le + 1) - b[RS(dq)].zh1;
b[LS(dq)].zh1 = x * (b[LS(dq)].ri - b[LS(dq)].le + 1);
b[LS(dq)].zh0 = (b[LS(dq)].ri - b[LS(dq)].le + 1) - b[LS(dq)].zh1;
b[LS(dq)].lazyf = b[RS(dq)].lazyf = false;
}
if (b[dq].lazyf)
{
b[LS(dq)].lazyf = !b[LS(dq)].lazyf;
b[RS(dq)].lazyf = !b[RS(dq)].lazyf;
swap(b[LS(dq)].zh0, b[LS(dq)].zh1);
swap(b[RS(dq)].zh0, b[RS(dq)].zh1);
}
b[dq].lazy01 = 2;
b[dq].lazyf = false;
}

/*
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

(2, 3)

1 2 3 4 5 6 7 8 9 0 1 2 3
0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5

0 0 0 1 1 1 1 1 1 1 1 1 0
0 0 0 1 1 1 1 0 1 1 1 1 0
0 0 0 1 1 0 0 1 0 0 1 1 0
0 0 0 0 0 1 1 0 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0


// 每个数要拆成两个来确定开闭区间
// U: 修改给定区间为1
// I: 修改非给定区间为0
// D: 修改给定区间为0
// C: 修改非给定区间为0, 给定区间内取反
// S: 给定区间取反
*/

By 被奶死的 Cansult