wth2026's blog

记录我的学校生活

发表于 更新于

日志

  • 2025-4-7，心血来潮开了一个博客，当时仅内网（即机房内可见）；

  • 2025-4-8，更新博客主题为NexT；

  • 2025-4-9，处理隐私问题，将所有人名换为【？？？】，为博客发布公网做准备；

  • 2025-4-10，征求博客出现的同学同意，将一部分同学名称换为定制名称，并发布公网；

  • 2025-4-11，解决隐私问题，更新日志，添加评论系统，打算更新，并成功弄炸配置文件；

  • 2025-4-12，所有配置被重置，重新开启博客，发现评论区炸掉；修复评论区。

所有对博客的建议，或bug反馈，请以在此日志下评论。

公告

博主学乖了，这辈子都不开LaTeX了QAQ

正在修复评论区。

Upd：修好了。

发表于

感谢所有祝福我的朋友们。特别感谢中午陪我去发疯的那些。

从我还没醒就有早起的朋友陆陆续续的给我发生日祝福，确实挺感动的。

昨天晚上没睡好，不嘻嘻。李老师建议我晚上听点东西。这下就有正大光明的理由睡觉听歌了。

第 $15.5$ 个信息竞赛生一大早就开始筹备中午带哪些人去发疯了。给王老师请假的也比较顺利，虽然我不用请假因为本来中午就不在学校，但是其他十个左右的同学需要。

可恶奶龙 居然不看在我的生日的份上给我们减作业，不嘻嘻。

中午提前下课，龟速赶到原班去见其他同学。不过没见到三个主课老师。

中午在 KFC 发疯。饮料和甜品的摄入量顶我一周了，简直太糖了。两杯咖啡，我感觉今晚我需要安眠药。

狗屎数学考试令人汗颜。为了不影响心情干脆不交了。

踢球两球两助，见到了 Linkwish。感谢邓智儿的两个喂到嗓子眼的单刀。

似乎是过得最快的一天，因为确实一直挺高兴的。

就不对我的 $13$ 岁做总结了，还是展望未来让人更有希望。

  • 希望我的竞赛能够学好。希望刷题量能够正贡献。希望这个赛季是四个一等。希望能在 RT 榜上的排名比较好看。我感觉我很容易陷入无意义的纠结当中，导致浪费时间。我也发现我只要静下心来慢慢弄，很多问题都是能克服的，我就是太毛毛躁躁了。我这个人很倔强，我相信，并且我就是要证明只要我静下来慢慢弄，我是能够在竞赛上学得还行的。

  • 希望我的综合不要再拉跨下去了。我感觉我来 数据删除 这边过后就是明显的那种感觉，我会做题，但我就是低分仔。希望我的综合至少能够进两次前二十吧。

  • 希望我和我的朋友们能够天天开心，希望我们都能有良好的心态，良好的睡眠，良好的身体，良好的成绩。也希望我的朋友们一如既往的包容我，我可能真的控制不住自己的情绪，但我冷静下来后一定会尽量弥补的，我也会尽我所能对你们好。当然如果你们有什么心理上的问题，又足够信任我的话，我也可以帮你们调节。虽然我自己的心理也不是很良好，但我绝对能做一个很好的倾听者和帮助者的。

这可能是我第一次在网上说出自己的愿望吧。再次感谢我的老师，朋友们，谢谢你们。

加油吧。

发表于 更新于

前情提要

博主即将迎来 14 岁生日，时间：2025/4/20

注：大家有没有发现这个日子还是某历史知名人物的生日；
又注：我说的是祖冲之，你在想什么？
又注：这个日子还是性别平等教育日，还是国际大麻合法化宣传日 ，还是（+30°~+45°）的生日。

由于 4 月 20 日博主要上课，所以将派对定在 4 月 19 日 （虽然 4 月 19 日也要上课）。

我们成功的邀请到了高一【撸竜Rhus中学】空气竞赛的高一学姐【？？？gy】，初三【Rhus中学】化学竞赛的大蛇【？？？cs】，初二【撸竜Rhus中学】的手风琴大蛇【？？？ce】，以及初一【？？？中学】生物竞赛的【？？？cy】和 a lot of xxs。

行程安排

在一神秘地点，早上或上午，【？？？gy】、【？？？ce】、【？？？cy】以及一众 xxs 先行到场，吃中午饭，下午开始玩。

17：00，我以及【？？？cs】下课，预计在17：05在楼下乒乓球台碰面，17：10在校门口坐上【？？？cs】’s mother’s car，到神秘地点；

然后疯狂吃晚饭；

然后疯狂玩；

然后第二天疯狂补whk作业。

QAQ……

实际行程

鸽鸽鸽，周天再写。

17:07坐上了车；

大概 ??:?? 的时候到了神秘地点，意外发现人比我预想得多，爽了；

和化竞大蛇开了一把台球，险胜；

然后和手风琴大蛇打拳王，决胜局被丝血反杀，惜败；

和化竞大蛇开实况足球，我一个不到 2800 的破队，游玩时间不足 3h，和他一个天天踢实况的人打了 3 个 0-0，他破防了……

吃饭，不好吃，据说每个人平均还花了 30 左右，bxx；

化竞大蛇不服，继续和我开实况，结果 7 个 0-0，1 个 1-1，成功将他破防；

听手风琴大蛇拉手风琴，好听好听，然后才后知后觉的发现我只会弹两首钢琴曲了，QAQ；

和高三大佬打台球，我花，他纯。花还有 6 颗的时候纯只剩 1 颗了，结果他没看见他还剩一颗直接把黑八捅进洞了，莫名其妙的赢了，xx；

去观摩老辈子打麻将，发现牌完全不是顺的，看不懂QAQ；

高二高三大佬台球互掐，不相上下；

和手风琴大蛇开台球，结果他第二杆就把黑八捅进去了，赢得莫名其妙（貌似是我开球力度太小，正好 4 库，球堵成一坨，他决定再开一下，结果黑八进去了）；

又和手风琴大蛇开了一把台球，他进黑八时我还剩两颗，过于强悍；

陪外公唱歌，发现外公中气好足；

去看无人机表演，结果堵车了，只看到一点点，bxx，还好是免费的，xx；

和手风琴大蛇、化竞大蛇、初一某人去开了 8 把麻将，赢 17 张，太棒了；

陪 xxs 玩双人成行，遇到有一关，就是磁铁之类的道具，发现可以打雪仗的彩蛋，于是疯狂捣乱；

和高一学姐陪 xxs 和某初一玩星之卡比，角色好像是把裤子套头上的小丑，发现可以在空中扔炸弹，于是偷了个电属性疯狂开路，屏幕一直金黄一片，卡比整局都没有吃到角色；

看另外一个初一玩原神，看不懂；

和六年级打台球，让了她 13 颗自由球，还是赢了；

玩重返小号，正好看到酒神颂，WWW；

准备把神秘地点的电脑弄一个客户端的，结果它无法公网联入，生气，暴力翘神秘地点的路由器，未遂；

坐车回家，睡觉。（此时 2：30）

离谱事迹

鸽鸽鸽，周天再写。

在坐车路上顺便给化竞大蛇推销了我的博客（发现他的手机无法连接github的我顺手帮他开了一个 VPN），看到逆天言论中 39 名言：

我一直以为检查装置气密性的原理是双手紧握试管，使试管发生轻微形变。

决定第二天踢球的时候嘲讽 39，又说到我们年级的化竞，被他疯狂嘲讽了（他说我们这一届的化竞全是脑瘫）；

吃饭的时候惊奇的发现我们的沙雕数学老师居然是他们班主任，有点震惊，于是给他说了他的B站账号，结果发现数学老师的B站账号是3.5个字（7个字符），搜索前两个字，自动补全第一个直接出现了老师的B站账号（可能是由于上次他的B站账号用户名暴露，我们搜索了200+次导致的），结果他把他的收藏夹全部清空了。但我们在他的关注里发现了一个叫性无限工作室的账号，上面有一条视频，我记得是他以前收藏了的，题目是“如何科学的增长阴茎长度”，震惊；

去看无人机表演的路上还是坐的化竞大蛇的车。化竞大蛇和其母坐的前面，我和手风琴大蛇坐的后面。意外发现后排中间的座椅靠背居然可以拆下来，又意外发现靠背里面有一块平板，还意外发现平板有车子声音大小、氛围灯、天窗和遮阳帘的最高控制权限，于是车子里的音乐一阵大一阵小，灯光闪烁不定，天窗时开时关，遮阳帘半起半落；

未完待续，等待图片上传ing……

发表于 更新于

规则

将所有名字不分队放到一个竞技场中，进行 5 轮乱斗，记下每个人的得分，最后存活的人额外加 500 分。

定义一场的苦劳力为不加成当场得分最高的人；

定义一场的MVP为加成当场得分最高的人；

定义一场的狗王为最后存活的人。

定义全场的苦劳力为不加成全场得分和最高的人；

定义全场的MVP为加成全场得分和最高的人；

定义全场的狗王为狗王次数最多的人，如有多个，则将他们全部放入一场新的乱斗，取最后存活的人。

目前报名：

投稿人 一号 二号 三号 四号
投稿人1号 wangtaohan988 wangtaohan693 wth500 wth777
投稿人2号 zhy2025 dhk2025 无 无
投稿人3号 gsx gsxbulb gsx0247 无
投稿人4号 名字竞技场 CA 无 无
投稿人5号 左岸 无 无 无
投稿人6号 zpz866 无 无 无
投稿人7号 Arctan26 AixcGHac Chat ydwr
投稿人8号 BSCZE 程至恩 无 无
投稿人9号 tianhaoxin huwenzhi tiahaoxin0324 realmadrid9248
投稿人10号 H2OShui h2oshuio3 无 无
投稿人11号 一抹浅念 无 无 无
投稿人12号 BJNR 无 无 无
投稿人13号 czr czr2012 这两个可以吧 无
投稿人14号 xiangqizhen214 xiangqizhen732 xiangqz586 我写了两个一样的怎么没人提醒我啊！11
投稿人15号 Acheron Cocytus Styx Phlegethon

名字集合

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
wangtaohan988
wangtaohan693
wth500
wth777
zhy2025
dhk2025
gsx
gsxbulb
gsx0247
名字竞技场
CA
左岸
zpz866
Arctan26
AixcGHac
Chat
ydwr
BSCZE
程至恩
tianhaoxin
huwenzhi
tiahaoxin0324
realmadrid9248
H2OShui
h2oshuio3
一抹浅念
BJNR
czr
czr2012
这两个可以吧
xiangqizhen214
xiangqizhen732
xiangqz586
我写了两个一样的怎么没人提醒我啊！11
Acheron
Cocytus
Styx
Phlegethon

投稿直接在下方评论即可，一个账号最多4个。

Upd: 现在出现了一个小小的问题，就是博主不知道如何改种子QAQ；评论区征集方法，啥时候征集到啥时候开。

Upd：现在会了，但可能又得鸽到周末了QAQ，这不能怪我。

发表于 更新于

qqr做题，试图暴力卡过去，然后……

这告诉我们，卡常，即使1ms，也要好好卡/kl

发表于

@nxd_oxm，作为一个从来都没有听过政治课，把政治课看为自习课的人，今天被叫起来回答问题。

@nxd_oxm理所应当的不会，于是去掏书。

至今没搞懂他是如何一脸镇静的摸出一本历史书的……

发表于 更新于

我操他马几把的傻逼玄学STL complex……

1
2
_Cmplx[j + k] += __ * _Cmplx[i + j + k];
_Cmplx[i + j + k] = _Cmplx[j + k] - complex <double> (2, 0) * __ * _Cmplx[i + j + k];

它 TLE 了

1
2
3
complex<double> x = _Cmplx[j + k], y = __ * _Cmplx[i + j + k];
_Cmplx[j + k] = x + y;
_Cmplx[i + j + k] = x - y;

他过了……

什么神经常数啊我靠……

发表于 更新于

鸽鸽鸽，下课再写。

Upd: 39：快点写，快点写，快点写……
Upd: 39：好好写你的博客，不要发私信。

周一是数竞外培回来的第一天，小T由于去医院了第一节课没有来，这时候小X发现她的椅子非常晃，于是就把小T的椅子换了一下。

第二节课小T来了，发现椅子非常晃，我于是就把小X换椅子的事情好心的告诉了他。他说：“没事，我不介意她和我换椅子，因为我在外培的时候做的对不起她的事情。”

我问：“你做了啥事情啊？”这时候【？】也把脑袋凑过来说：“啥啊，我也要听”

小T：“就是我们去外培的时候编了很多【睡前小故事】，然后我编了情节，【？？】编了细节。男主是【？？？】，女主就是她。”这番话被小X听到了。

由于作者要回家吃饭，于是乎中午回来的时候，看见走廊上站这两拨人，左边是【？？】和小T，右边是班主任和小X（身高差距&体型差距非常之……一点也不大）（高度疑似是小X告老师了）。

过了一会儿，吴大和小T走了回来，小X直接抄起东西跑到另外一个地方坐了。

小T：“我们的生存压力又小了很多。”（应为在那一圈5个人中，小T经常买零食，然后被5个人瓜分，可以形象的称之为以一己之力养活5个人，小X走了之后，他就只用以一己之力养活4个人了）

Upd：本文以第一人称视角写作，完全真实，0虚构内容。

发表于 更新于

1.工具

1.read（快读）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<20, stdin), p1 == p2) ? EOF : *p1 ++)
char *p1 ,*p2, buf[1 << 20 + 5];

inline int read() {
	int x = 0, f = 1;
	char c = gc();
	
	while (!isdigit(c)) {
		if (c == '-') {
			f *= -1;
		}
		
		c = gc();
	}
	
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = gc();
	}
	
	return x * f;
}

2.write（快输）

1
2
3
4
5
6
7
8
9
10
11
12
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	
	if (x > 9) {
		print(x / 10);
	}
	
	putchar('0' + x % 10);
}

2.数据结构

1.Heap(堆)

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
struct Heap {
	int h[1000005], size;
	
	void clean() {
		memset(h, 0, sizeof(0));
		size = 0;
	}
	
	void down(int u) {
		int t = u;
		
		if (u * 2 <= size && h[u * 2] < h[t]) {
			t = u * 2;
		}
		
		if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) {
			t = u * 2 + 1;
		}
		
		if (u != t) {
			swap(h[u], h[t]);
			down(t);
		}
	}
	
	void up(int u) {
		while (u / 2 > 0 && h[u / 2] > h[u]) {
			swap(h[u / 2], h[u]);
			u /= 2;
		}
	}
	
	int top() {
		return h[1];
	}
	
	void push(int k) {
		h[++ size] = k;
		up(size);
	}
	
	void pop() {
		h[1] = h[size];
		-- size;
		down(1);
	}
};

2.BIT(树状数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct BIT {
	int c[500005], n;
	
	int loubit(int s) {
		return s & -s;
	}
	
	void add(int k, int x) {
		for (int i = k; i <= n; i += loubit(i)) {
			c[i] += x;
		}
	}
	
	int ask(int k) {
		int ans = 0;
		
		for (int i = k; i; i -= loubit(i)) {
			ans += c[i];
		}
		
		return ans;
	}
};

3.FHQ Treap（无旋平衡树）

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
template <size_t N>
	class FHQ_Treap {
		private :
			int cnt = 0, root = 0, dl = 0, dr = 0, temp = 0;
			
			struct treap {
				int l, r, key, pro, num, size;
			} tr[N + 5];
			
			void pushup (int k) {
				tr[k].size = tr[tr[k].l].size + tr[tr[k].r].size + 1;
			}
			
			int newtreap (int x) {
				tr[++ cnt].key = x;
				tr[cnt].pro = rand ();
				tr[cnt].num = tr[cnt].size = 1;
				return cnt;
			}
			
			void split (int pos, int xx, int& l, int& r) {
				if (!pos) {
					l = r = 0;
					return;
				}
				
				if (tr[pos].key <= xx) {
					l = pos;
					split (tr[l].r, xx, tr[l].r, r);
				} else {
					r = pos;
					split (tr[r].l, xx, l, tr[r].l);
				}
				
				pushup (pos);
			}
			
			int merge (int l, int r) {
				if (!l || !r) {
					return l | r;
				}
				
				if (tr[l].pro <= tr[r].pro) {
					tr[l].r = merge (tr[l].r, r);
					pushup (l);
					return l;
				} else {
					tr[r].l = merge (l, tr[r].l);
					pushup (r);
					return r; 
				}
			}
			
		protected :
		
		public :
			void Insert (int xx) {
				split (root, xx - 1, dl, dr);
				root = merge (merge (dl, newtreap (xx)), dr);
			}
			
			void Delete (int xx) {
				split (root, xx - 1, dl, dr);
				split (dr, xx, temp, dr);
				temp = merge (tr[temp].l, tr[temp].r);
				root = merge (dl, merge (temp, dr));
			}
			
			int Get_Rank (int xx) {
				split (root, xx - 1, dl, dr);
				int rank = tr[dl].size + 1;
				root = merge (dl, dr);
				return rank;
			}
			
			int Get_Num (int pos, int k = root) {
				int lsize = tr[tr[pos].l].size + 1;
				
				if (lsize == k) {
					return tr[pos].key;
				}
				
				if (lsize > k) {
					return Get_Num (tr[pos].l, k);
				} else {
					return Get_Num (tr[pos].r, k - lsize);
				}
			}
			
			int Get_Last (int xx) {
				split (root, xx - 1, dl, dr);
				int last = Get_Num (dl, tr[dl].size);
				root = merge (dl, dr);
				return last;
			}
			
			int Get_Next (int xx) {
				split (root, xx, dl, dr);
				int next = Get_Num (dr, 1);
				root = merge (dl, dr);
				return next;
			}
			
			void Delete_All (int k) {
				int _1, _2, _3, _4;
				split (root, k - 1, _1, _2);
				split (_2, k, _3, _4);
				merge (_1, _4);
			}
		
	} ;

4.Splay(旋转BST)

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
struct Splay {
	int root, cnt;
	
	struct Node {//节点 
		int tree_size, size, val, fa, son[2];
	} tr[N + 5];
	
	void Push_Up(int k) {//上传标记 
		tr[k].tree_size = tr[tr[k].son[0]].tree_size + tr[tr[k].son[1]].tree_size + tr[k].size;
	}
	
	int Get(int x) {//求是那个儿子 
		if (x == tr[tr[x].fa].son[0]) {
			return 0;
		} else {
			return 1;
		}
	}
	
	void rotate(int x) {//旋转 
		int y = tr[x].fa, z = tr[y].fa, d = Get(x);
		tr[y].son[d] = tr[x].son[d ^ 1];

		if (tr[x].son[d ^ 1]) {
			tr[tr[x].son[d ^ 1]].fa = y;
		}

		tr[x].son[d ^ 1] = y;
		tr[y].fa = x;

		if (z) {
			tr[z].son[y == tr[z].son[1]] = x;
		}

		tr[x].fa = z;
		Push_Up(y);
		Push_Up(x);
	}
	
	void splay(int x) {//伸展 
		while (tr[x].fa) {
			int y = tr[x].fa, z = tr[y].fa;

			if (z) {
				if (Get(x) ^ Get(y)) {
					rotate(x);
				} else {
					rotate(y);
				}
			}

			rotate(x);
		}

		root = x;
	}
	
	int Get_Rank(int x) {//求一个数的排名 
		int k = root, res = 1;

		while (k) {
			if (x == tr[k].val) {
				res += tr[tr[k].son[0]].tree_size;
				splay(k);
				return res;
			}

			if (x < tr[k].val) {
				k = tr[k].son[0];
			} else {
				res += tr[tr[k].son[0]].tree_size + tr[k].size;
				k = tr[k].son[1];
			}
		}

		return res;
	}
	
	int Get_Num(int x) {//求一个排名的数 
		int k = root;

		while (k) {
			int _ = tr[tr[k].son[0]].tree_size;

			if (x <= _) {
				k = tr[k].son[0];
			} else if (_ + tr[k].size >= x) {
				break;
			} else {
				x -= _ + tr[k].size;
				k = tr[k].son[1];
			}
		}

		splay(k);
		return tr[k].val;
	}
	
	void Insert(int x) {//插入一个数 
		if (!root) {
			root = ++ cnt;
			tr[root].tree_size = tr[root].size = 1;
			tr[root].val = x;
			return;
		}

		int _ = 0, k = root;

		while (k) {
			if (x == tr[k].val) {
				break;
			}

			_ = k;
			k = tr[k].son[x > tr[k].val];
		}

		if (!k) {
			k = ++ cnt;
			tr[_].son[x > tr[_].val] = k;
			tr[k].fa = _;
			tr[k].val = x;
		}

		++ tr[k].size;
		Push_Up(k);
		Push_Up(_);
		splay(k);
	}
	
	
///	void Insert(int k) {//插入 
//		if (!root) {
//			tr[++ cnt].val = k;
//			++ tr[cnt].size;
//			root = cnt;
//			Push_Up(cnt);
//			return;
//		}
//		
//		int _ = root, f = 0;
//		
//		while (1) {
//			if (tr[_].val == k) {
//				++ tr[_].size;
//				Push_Up(_);
//				Push_Up(f);
//				splay(_);
//				break;
//			}
//			
//			f = _;
//			_ = tr[_].son[tr[_].val < k];
//			
//			if (!_) {
//				tr[++ cnt].val = k;
//				++ tr[cnt].size;
//				tr[cnt].fa = f;
//				tr[f].son[tr[_].val < k] = cnt;
//				Push_Up(cnt);
//				Push_Up(f);
//				splay(cnt);
//				break;
//			}
//		}
//	}
//	
	void Delete(int x) {//删除一个数 
		int _ = 0, k = root;

		while (k) {
			if (x == tr[k].val) {
				break;
			}

			_ = k;
			k = tr[k].son[x > tr[k].val];
		}

		splay(k);

		if (tr[k].size == 1) {
			int p = tr[k].son[0];

			if (!p) {
				root = tr[k].son[1];
				tr[root].fa = 0;
				return;
			}

			while (tr[p].son[1]) {
				p = tr[p].son[1];
			}

			splay(p);
			tr[p].son[1] = tr[k].son[1];
			tr[tr[k].son[1]].fa = p;
			Push_Up(p);
		} else {
			-- tr[k].size;
			Push_Up(k);
		}
	}
	
	void Delete_All(int x) {//删除一个数的所有 
		int _ = 0, k = root;
	
		while (k) {
			if (x == tr[k].val) {
				break;
			}
	
			_ = k;
			k = tr[k].son[x > tr[k].val];
		}
	
		splay(k);
		int p = tr[k].son[0];
		
		if (!p) {
			root = tr[k].son[1];
			tr[root].fa = 0;
			return;
		}
	
		while (tr[p].son[1]) {
			p = tr[p].son[1];
		}
			
		splay(p);
		tr[p].son[1] = tr[k].son[1];
		tr[tr[k].son[1]].fa = p;
		Push_Up(p);
	}
	
	int Get_Last(int x) {//求一个数的前驱 
		Insert(x);
		int k = tr[root].son[0];

		while (tr[k].son[1]) {
			k = tr[k].son[1];
		}

		splay(k);
		Delete(x);
		return tr[k].val;
	}
	
	int Get_Next(int x) {//求一个数的后继 
		Insert(x);
		int k = tr[root].son[1];

		while (tr[k].son[0]) {
			k = tr[k].son[0];
		}

		splay(k);
		Delete(x);
		return tr[k].val;
	}
}

5.Persistent Segment Tree(可持久化线段树)

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
struct Persistent_Segment_Tree {
	int Root[N + 5], cnt, Root_Num;
	
	struct Node {
		int l, r, lson, rson, val;
	} tr[(N << 5) + 5];
	
	//---------------------------------
	
	int New_Node() {
		return ++ cnt;
	}
	
	void Init() {
		cnt = 0;
		Root_Num = 0;
		Root[0] = New_Node();
	}
	
	void build(int k, int l, int r, int a[]) {
		tr[k].l = l;
		tr[k].r = r;
		
		if (l == r) {
			tr[k].val = a[l];
			return;
		}
		
		tr[k].lson = New_Node();
		tr[k].rson = New_Node();
		int mid = (l + r) >> 1;
		build(tr[k].lson, l, mid, a);
		build(tr[k].rson, mid + 1, r, a);
	}
	
	void edit(int k, int x, int v) {
		if (tr[k].l == tr[k].r) {
			tr[k].val = v;
			return;
		}
		
		int mid = tr[tr[k].lson].r;
		Node _;
		
		if (x <= mid) {
			_ = tr[tr[k].lson];
			tr[k].lson = New_Node();
			tr[tr[k].lson] = _;
			edit(tr[k].lson, x, v);
		} else {
			_ = tr[tr[k].rson];
			tr[k].rson = New_Node();
			tr[tr[k].rson] = _;
			edit(tr[k].rson, x, v);
		}
	}
	
	int query(int k, int x) {
		if (tr[k].l == tr[k].r) {
			return tr[k].val;
		}
		
		int mid = tr[tr[k].lson].r;
		
		if (x <= mid) {
			return query(tr[k].lson, x);
		} else {
			return query(tr[k].rson, x);
		}
	}
	
	void Build(int n, int a[]) {
		build(Root[0], 1, n, a);
	}
	
	void Edit(int x, int v, int opt) {
		Root[++ Root_Num] = New_Node();
		tr[Root[Root_Num]] = tr[Root[opt]];
		edit(Root[Root_Num], x, v);
	}
	
	int Query(int opt, int x) {
		Root[++ Root_Num] = New_Node();
		tr[Root[Root_Num]] = tr[Root[opt]];
		return query(Root[Root_Num], x);
	}
}

3.组合数学

1.C

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
int ksm(int a, int b, int mod) {
    int ans = 1;

    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }

        a *= a;
        a %= mod;
        b >>= 1;
    }

    return ans;
}

int jc[300005];

void init(int mod) {
    jc[0] = 1;

    for (int i = 1; i < 300005; ++ i) {
        jc[i] = jc[i - 1] * i % mod;
    }
}

int C(int _, int __, int mod) {
	if (_ < __) {
		return 0;
	}
	
    return jc[_] * ksm(jc[__], mod - 2, mod) % mod * ksm(jc[_ - __], mod - 2, mod) % mod;
}

4.图论

1.Tarjan（无向图）

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
#define Min(x,y) (x=min(x,y))
int dfn[N], low[N], cnt, SCC[N], _Sz[N];
bool _Flg[N];
stack <int> _Stck;
vector <int> _Mp[N];

void tarjan (int id, int fa) {
	if (dfn[id]) {
		if (_Flg[id]) {
			Min (low[fa], dfn[id]);
		}
		
		return ;
	}
	
	dfn[id] = ++ cnt;
	low[id] = dfn[id];
	_Stck.push (id);
	_Flg[id] = 1;
	
	for (auto it : _Mp[id]) {
		if (it ^ fa) {
			tarjan (it, id);
			Min (low[id], low[it]);
		}
	}
	
	if (dfn[id] == low[id]) {
		++ SCC[0];
		
		while (_Stck.top () ^ id) {
			SCC[_Stck.top ()] = SCC[0];
			++ _Sz[SCC[0]];
			_Flg[_Stck.top ()] = 0;
			_Stck.pop ();
		}
		
		SCC[_Stck.top ()] = SCC[0];
		++ _Sz[SCC[0]];
		_Flg[_Stck.top ()] = 0;
		_Stck.pop ();
	}
}

2.费用流

1) EK

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
class Edge {
  private :
  
  protected :
  
  public :
    int to, v, w, c;
    
    void operator () (int T, int V, int W, int C) {
      to = T;
      v = V;
      w = W;
      c = C;
    }
    
    int& operator ~ () {
      return to;
    }
    
    int& operator ! () {
      return v;
    }
    
    int& operator & () {
      return w;
    }
    
    int& operator * () {
      return c;
    }
  
} ;

const int N = 5e3 + 5, M = 1e5 + 5;

int n, m, s, t;
int u, v, w, c;
int cnt, h[N];
Edge _Mp[M];
int _Ds[N], _Pth[N], _Flw_Cst[N];
bool _Flg[N];
int _Mx_Flw, _Mn_Cst;
queue <int, list <int>> _Q;
int _;

void Add_Edge (int U, int V, int W, int C) {
  _Mp[++ cnt] (h[U], V, W, C);
  h[U] = cnt;
}

void Add_Flow (int U, int V, int W, int C) {
  Add_Edge (U, V, W, C);
  Add_Edge (V, U, 0, -C);
}

bool SPFA () {
  memset (_Ds, inf, sizeof (_Ds));
  memset (_Flg, 0, sizeof (_Flg));
  
  while (_Q.size ()) {
    _Q.pop ();
  }
  
  _Q.push (s);
  _Ds[s] = 0;
  _Flw_Cst[s] = lnf;
  _Flw_Cst[t] = 0;
  
  while (_Q.size ()) {
    _ = _Q.front ();
//			cout << "\t" << _ << endl;
    _Q.pop ();
    _Flg[_] = 0;
    
    for (register int i = h[_]; i; i = (~ _Mp[i])) {
      if (! (& _Mp[i]) || _Ds[! _Mp[i]] <= _Ds[_] + (* _Mp[i])) {
        continue ;
      }
      
      _Ds[! _Mp[i]] = _Ds[_] + (* _Mp[i]);
      _Flw_Cst[! _Mp[i]] = min ((& _Mp[i]), _Flw_Cst[_]);
      _Pth[! _Mp[i]] = i;
      
      if (! _Flg[! _Mp[i]]) {
        _Q.push (! _Mp[i]);
        _Flg[! _Mp[i]] = 1;
      }
    }
  }
  
  return _Flw_Cst[t];
}

void Edit () {
  _Mx_Flw += _Flw_Cst[t];
  
  for (register int i = t; i ^ s; i = (! _Mp[_Pth[i] ^ 1])) {
    (& _Mp[_Pth[i]]) -= _Flw_Cst[t];
    (& _Mp[_Pth[i] ^ 1]) += _Flw_Cst[t];
    _Mn_Cst += _Flw_Cst[t] * (* _Mp[_Pth[i]]);
  }
}

5.数学

1.傅里叶变换

1)分治DFT

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
const int N = (1 << 21) + 5;
const double pi = acos (-1.0);
const complex <double> I (0, 1);

complex <double> a[N], b[N], _Tmp[N], _, __;

void DFT (complex <double> * _Cmplx, int n, int re) {
	if (n == 1) {
		return ;
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		_Tmp[i] = _Cmplx[i];
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		if (i & 1) {
			_Cmplx[(i >> 1) + (n >> 1)] = _Tmp[i];
		} else{
			_Cmplx[(i >> 1)] = _Tmp[i];
		}
	}
	
	DFT (_Cmplx, n >> 1, re);
	DFT ((_Cmplx + (n >> 1)), n >> 1, re);
	
	_  = complex <double> (cos (2 * pi / n), sin (2 * pi * re / n));
	__ = complex <double> (1, 0);
	
	for (register int i = 0; i ^ (n >> 1); ++ i) {
		_Tmp[i] = _Cmplx[i] + __ * _Cmplx[i + (n >> 1)];
		_Tmp[i + (n >> 1)] = _Cmplx[i] - __ * _Cmplx[i + (n >> 1)];
		__ *= _;
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		_Cmplx[i] = _Tmp[i];
	}
}

int n, m;
//	int IO;
int nm;

void Main () {
	nm = 1;
	cin >> n >> m;
	
	while (nm <= n + m) {
		nm <<= 1;
	}
	
	for (register int i = 0; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (register int i = 0; i <= m; ++ i) {
		cin >> b[i];
	}
	
//		for (register int i = 0; i <= n; ++ i) {
//			cout << '\t' << i << ' ' << a[i] << endl;
//		}
//		
//		cout << nm << endl;
	DFT (a, nm, 1);
	DFT (b, nm, 1);
	
	for (register int i = 0; i <= nm; ++ i) {
		a[i] *= b[i];
	}
	
	DFT (a, nm, -1);
	
	for (register int i = 0; i <= n + m; ++ i) {
		cout << (int) (floor ((a[i].real () / nm) + 0.5)) << ' ';
	}
	
	cout << endl;
}

2）倍增FFT

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
const int N = (1 << 21) + 5;
const double pi = acos (-1.0);

int n, m;
int nm;
complex <double> a[N], b[N], _, __;
int l, r[N];

void FFT (complex <double> * _Cmplx, int re) {
	for (register int i = 0; i ^ nm; ++ i) {
		if (i < r[i]) {
			swap (_Cmplx[i], _Cmplx[r[i]]);
		}
	}
	
	for (register int i = 1; i ^ nm; i <<= 1) {
		_ = complex <double> (cos (pi / i), sin (pi / i) * re);
		
		for (register int j = 0; j ^ nm; j += (i << 1)) {
			__  = complex <double> (1, 0);
			
			for (register int k = 0; k ^ i; ++ k) {
				complex<double> x = _Cmplx[j + k], y = __ * _Cmplx[i + j + k];
				_Cmplx[j + k] = x + y;
				_Cmplx[i + j + k] = x - y;
				__ *= _;
			}
		}
	}
}

void Main () {
	nm = 1;
	l = 0;
	cin >> n >> m;
	
	while (nm <= n + m) {
		nm <<= 1;
		++ l;
	}
	
	for (register int i = 0; i ^ nm; ++ i) {
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	}
	
	for (register int i = 0; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (register int i = 0; i <= m; ++ i) {
		cin >> b[i];
	}
	
	FFT (a, 1);
	FFT (b, 1);
	
	for (register int i = 0; i <= nm; ++ i) {
		a[i] *= b[i];
	}
	
	FFT (a, -1);
	
	for (register int i = 0; i <= n + m; ++ i) {
		cout << (int) (floor ((a[i].real () / nm) + 0.5)) << ' ';
	}
	
	cout << endl;
}

6.其他算法

1.Bsearch(二分)

1）寻找满足check() == true的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Bsearch(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        
        if (check(mid)) {
        	r = mid;
        }
        else {
        	l = mid + 1;
        }
    }
    
    return l;
}

2）寻找满足check() == true的最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Bsearch(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        
        if (check(mid)) {
        	l = mid;
        }
        else {
        	r = mid - 1;
        }
    }
    
    return l;
}