寫在前面：

因爲 Feed，寫完之後被發到羣裏給大家欣賞了一番。

經過競標後更改了標題。

原標題：数据结构专题略解

一个数据结构的专题题解。

无详有略。

有些题可能以后会单独写一篇。

虽然是校内的专题但是都是在洛谷上面抓的就不加密了。

相逢是问候

势能线段树。

考虑使用扩展欧拉定理，发现每个数每次操作只会进行 $\log$ 级别，于是大力修改即可。

注意预处理快速幂，这样可以减少一个 $\log$。

楼房重建

首先转化成斜率。

问题就变成了找一个从头开始的上升序列。

考虑线段树维护，合并左右儿子的递归的时候，二分右儿子记录贡献即可。

二分图 /【模板】线段树分治

板子题，思路是把操作离线，挂在一颗线段树上面即可。

岛屿探险

我不会，但我会指令集直接暴力草过去。

归程

以海拔为关键字从大到小构建 Kruskal 重构树，这样在水位小于节点权值的情况下同一个子树内是可以互相到达的。

于是记录每个子树到 $1$ 节点的距离，然后倍增查找即可。

可持久化并查集

板子题，直接做即可。

注意使用按秩合并。

整数序列

懒得写了

Count on a tree II/【模板】树分块

模板题，看这个还不如去洛谷看题解。

二逼平衡树（树套树）

模板题，如果外面的线段树是开在值域上的可以少个 $\log$。

维护数列

文艺平衡树基本运用，写完这个就差不多过关了，可以再加个银河英雄传说V2。

密码箱

首先发现不用约分。

考虑将分数转化为矩阵，这样对于 $f$ 就可以快速求值。

然后发现对于 $W,E$ 两种操作都可以使用一个矩阵来表示。

开颗文艺平衡树来维护即可。

宝石

这篇题解写得挺好的，但是貌似被叉了？

The Tree

我们称 $1$ 操作为「晕开」，$2$ 操作为「清空」。

发现朴素晕开的时间复杂度我们受不了 qwq，尝试用树剖方式与询问摊一下。

若在一个位置晕开一次黑色，我们就单点加 $1$，若所有的初始点权均为 $-1$，则单点询问 $x$ 时相当于问：

从根到 $x$ 路径上的点权的最大后缀和（不可空）是否 $\ge0$。

原因是每个点要消耗一个单位，所以初始值为 $−1$，而每次晕开相当于向下多扩展 $1$。

清空 $x$ 如何？首先我们要让 x 子树内的点权均清空为 $−1$，然后要阻断此时从上层来的墨量，所以用 $x$ 「吸收」，即 x 点权再减 x 处的询问值再 $−1$。

询问则树剖跳链，线段树维护区间和，区间最大后缀和即可。

——來自洛谷題解。

Bear and Bowling

不會，但 C++20 幫我草過去了。

你的名字。

大分塊，还卡常，建议看分块入门。

Breadboard Capacity (hard version)

整个专题最有趣的题。

首先考虑网络流，蓝色连原点，红色连汇点，然后中间的格子连四联通。

首先肯定过不去，考虑模拟网络流。

因为最大流等于最小割，再加上一些性质，就可以做 DDP 了。

Fusion tree

一个 trick，一起维护儿子，暴力维护父亲。

于是就是维护全局异或和，修改以及全局加一。

用 trie 维护即可。

模仿校内题解风格？