用到了曼哈顿距离和切比雪夫距离的转化，对于这种需要旋转坐标系的问题非常有帮助，然后就是发现相对位置是不变的，所以直接前缀加单点查，树状数组维护即可。

直接写了个大力线段树维护，每次操作区间赋值单点加，区间求和。

一个不错的树形 dp，考虑设 $f_{i,j}$ 表示 $i$ 子树内可达 $j$ 个点是否合法，转移根据 $l_u = l_v$ 分类讨论，然后按照每条边是否连通分类讨论即可。

发现对于最右边的每个点，能到达他的点是一段连续的区间，于是问题变成了给定 个区间 ， 次询问区间 ，询问覆盖区间 需要最少区间数量，可以直接倍增维护。具体的维护倍增从每个点出发，向后最远能到哪，然后跳倍增数组即可。

发现一个性质是，最大值要么是 $0$，要么是 $1$，于是问题变成我们需要找到有多少个区间满足 $mex = len + 1$，也就是整个区间排序后是 $0,1,2,3,4,\dots,len - 1$。

发现必须经过 $0$，于是考虑按每个 $0$ 分段处理，由于知道了区间最大值就可以知道区间长度，因此我们亲定最大值位于左边，右边的情况我们反转序列再做一遍即可。

之后我们考虑枚举左端点的位置，维护前后缀 $\max$，这样我们可以求出区间长度，也就求出了右端点位置，然后判断右端点的最大值是否合法，这样我们就只需要知道，这段区间是不是数字各不相同即可。

如何维护这个东西呢？其实可以直接对每个位置 $i$ 维护 $i$ 向后最远到哪能满足这段区间内每个数只出现一次，然后就做完了。

考虑把变化维护到折线上，每次分治暴力枚举区间，时间复杂度 $n \log n$，还需要主席树维护一下前后缀信息，具体的可以去看官解，感觉口胡太麻烦了。

反射容斥，还不会 \kk ~~。

考虑贪心的从大到小做，然后变成了一个二维数点？实则发现合法转移式子两个是肯定同时满足的，于是维护两个值，一个排序，另一个维护单调栈即可。

很简单的一个 dp，考虑设 $f_{i,0/1/2}$ 表示前 $i$ 个灯合法，最后一个是 $0/1/2$ 颜色的最小花费，转移是好写的，注意把 $f_{i,2}$ 初始化成前缀全都熄灭的花费即可。

很有难度的一个题。

首先你需要发现一个性质：每个雪球的贡献点是一段区间。

然后发现当两个雪球之间的区间端点确定了，就不会再变了，于是我们可以考虑暴力维护这个东西，复杂度 $O(nq)$。

考虑怎么优化呢？这一步非常困难，你发现这东西是具有可二分性的，二分最终确定端点的时间，就可以处理出每个端点，时间复杂度 $O(n \log q)$。

发现题目其实就是要让我们找一个上升子序列，我们发现对于 $i$ 能转移过来的 $j$ 是一段区间，我们可以用并查集维护这个东西，然后我们按照值从小到大去做，每次转移找到转移区间，线段树维护即可。

哇好牛的一个题，考虑最大的这个块一定要被挡住，然后考虑 dp。

设 $f_{i,j,0/1}$ 表示前 $i$ 列，有 $j$ 个位置是能照到的，有没有出现 $mx$ 长度的照不到区间，不需要移动的贡献和最大值，发现转移实际上时对于右端点位于 $i$ 的区间，覆盖到的范围加上一个它的权值，于是线段树维护即可。

哇这题太难了，我们发现当我们使用 $3$ 个数字一组，用 $4$ 组凑一个人，那么我们需要满足任意 $4$ 组组成的一个序列一定有一个人，否则我们可以先走这个东西，然后再走到某个位置，这样就确定不了一个必定赢的人了。

然后拿背包把这些合并起来即可，感觉代码太难写了，直接盒了。

简单题，考虑排序后双指针指一下即可。

发现排序后后面的是前面的倍数，类似一个进制形式的东西，同时发现这样的 $v$ 只会有 $\log$ 种，于是我们考虑对于 $v = a_i$ 如果他没被选中，可以把 $k$ 个合并成一个 $v = a_{i + 1}$ 的物品，同一类按照性价比选即可。

不会啊，反射容斥（刚刚那个 T3 好像不是反射容斥）。

发现这东西一定是从小到大推平，我们推出式子，发现从两边先搞一定是更优的，然后就是要维护前后缀最小值，区间修改，线段树维护即可。

考虑这东西可以二分，然后 check 考虑从后往前做，这样走到后面的人过来就不需要花费路程，只需要花费工时。

数据范围很小，状态数可以搞得下，直接搜索就行了。

简单题，发现答案是 $\max(x - y,z)$，这里 $x = \max(a_i),y = \min(a_i)$，$z$ 为严格次小。

考虑相当于是给了一些区间，要求最少集合，使得同一集合内区间不相交，线段树维护即可。

考虑数位 dp，然后统计答案即可。

将这棵树建出来之后，其实就是求树的直径。

感觉这题没啥营养啊，就是直接 $f_i$ 表示以 $i$ 结尾的最大权值，然后动态开店权值线段树维护 $dp$ 值即可。

图上 dp 板子题，按照 topu 序 dp。

整数拆分的模板，这个要好好看一下。

dsu on tree 好题，考虑两棵子树该如何合并，按照这种方式合并起来即可。

考虑从前往后维护一下当前最大值，貌似还可以 ODT？直接维护一下最大值和贡献区间即可。

几个简单的 tarjan。

感觉没什么好题，其中 E 是个大模拟，F 是组合数推式子，用组合恒等式优化一下就行了。