首先，如果 a 能到达 b，当且仅当编号为 a\sim b-1 的路灯都是亮着的。现在考虑当一个路灯 x 从亮到不亮，会对多少对 (a,b) 产生影响。很显然，对于所有 a \le x \land b>x 的 (a,b) 都会产生一定的影响。若 (a,b) 在 x 不亮之前就不连通了，则不变。否则变成不连通。
发现 m 十分小，考虑暴力 DP。定义状态函数 f_{i,j} 表示 i 为根的子树中，花费 j 的时间最多能得到的价值。因为我们是路径，所以需要保证我们选择的点形成连通块。那么对于 u 来说，它就是必选的了。那么对于选择 u 的一个儿子 v 的子树，u\to v 这条边也是必须经过的。有：f_{u,x}=\max\limits_{y=0}^{x-w} f_{u,y}+f_{v,x-y-w}。这个直接树上背包的时间复杂度是 O(mV) 的。
染上一个没有染过的点比较麻烦。不如直接染成 x，因为点的编号不同，不肯能有两个 x,y (x\ne y) 进行操作 1 得到了相同的值，且仅可能有 x 到根的路径上存在这个颜色。那么对于求 x 到 y 的路径价值，我们就可以树剖维护。对于线段树维护其左端点的颜色，右端点的颜色，这个区间的价值。合并的时候只要相邻的颜色有重复，说明颜色段需要 -1。对于查询 x 子树内点到根价值最大值，因为我们相同的颜色肯定是一个点到根路径的前缀。那么当我们进行赋值操作的时候，可以维护出每个颜色的起始位置与终点位置。当我们将 1 到 x 的路径覆盖时，一个完全被覆盖的颜色 c 就会对其子树的颜色产生 -1 的贡献。由于每个颜色最多被删除和添加共 O(n) 次，所以暴力维护即可。
注意到我们切下来的是一个四联通块。那么记 p_i 表示第 i 列被切的位置，则对于相邻两列，如果都切了，一定有 p_i \le \min(a_i,a_{i+1})\land p_{i+1} \le \min (a_i,a_{i+1})。然后就做完了。如果我们第 i 列是结尾，则 p_i \le \min(a_i,a_{i-1})，记 f_i 为从前 i 列的某一列开始切，且第 i+1 列要切的方案数。如果我们 i 切完就不切了，有：ans_i=\min(a_i,a_{i-1})\times f_{i-1}+a_i。如果我们不结束，还需要满足 p_i \le \min(a_i,a_{i+1})，那么有：f_i =\min(a_i,a_{i+1})+\min(a_i,a_{i-1},a_{i+1}) \times f_{i-1}。时间复杂度 O(n)。因为我们不能切完，所以这里钦定 a_i 为原 a_i-1。
CF1418G
唐诗。
有个典 trick，判定一段区间内每个数是否出现偶数次可以直接全部异或起来。只要是 0，大概率说明一个值 x 出现了偶数次。然后对每个值重新给个随机值错误率就极小。
那么这题可以直接仿照这个思路。考虑分治。我们对 x 出现 y 次给一个随机值。那么只需要满足分治中心左边每个数 x 出现 cnt_x 次的值与右边每个数 x 出现 3-cnt_x' 的值异或起来为 0 就大概率对。而因为一个数不能出现大于 3 次，所以我们对于每个枚举的起点应该有一个右端点的限制。则只需要维护区间内某个数的出现次数就能解决了。时间复杂度 O(n\log^2 n)。
CF1744F
考虑什么样的区间满足条件。区间内的中位数 x 一定有性质：区间内不大于 x 的数不小于区间长度的一半。那么对于一个满足条件的区间，因为 0\sim mex-1 全部出现过，所以 2 \times mex \ge len 时这个区间就是满足条件的区间。考虑枚举 mex，我们能够得到一个最小的区间 [l,r]，使得这个区间的 mex=x。记 p_i 为 a_j=i 的下标。那么当 p_{x} < l 时，只要我们 p_{x} <l' \le l \land r \le r' \le n \land 2\times x\ge r'-l'+1 就是一个合法的区间。p_{x}>r 同理。那么我们只需要枚举 l' 或 r' 就能得到所有合法区间的数量了。这里有个 trick，我们只需要每次枚举限制长度小的一边，就貌似是 O(n\log n) 的。具体我不会，但是跑得很快。
CF1702G1/G2
先不考虑 k 个节点的限制。考虑一棵树是否合法。既然我们每条边不能重复经过，那么最有策略显然是从一个叶子节点出发，走到另一个叶子节点。而对于一个中间节点，如果它的度数不小于 3，那么我们只能从它的其中一边走到它，在走到另外两边的一边，再回来走另一边。不难发现这显然会经过同样的边。那么这棵树合法当且仅当这棵树是条链。
注意到 \sum k \le 2\times 10^5。由于其它节点实际上是没有用的，我们直接建立虚树。那么只要这棵虚树是条链就合法了。时间复杂度 O(\sum k \log \sum k)。
CF323C
注意到这是两个排列。考虑对于每个值 x，记录 a,b 表示其在第一个和第二个排列中的位置。那么 x 会被算进答案当且仅当 l1 \le a \le r1\land l2 \le b \le r2。那么这就相当于查询一个矩形内散点的数量。直接主席树维护即可。时间复杂度 O((n+m)\log n)。
CF1370D
典 trick。对于找最小的值，我们可以考虑二分答案。将所有的 a_i \le mid 的点视为 1，其余视为 0。那么原问题就转化为：求是否存在一个长度为 k 的子序列，使得其奇数位全为 1 或偶数为全为 1。我们分开来讨论。拿前者举例，记 f_{i,0/1} 表示前 i 个数，当最后一位是偶数位或奇数位时能够凑出的最大长度，且满足选出的奇数位全为 1。那么有：f_{i,0}=\max(f_{i-1,0},f_{i-1,1}+1),f_{i,1}=\max(f_{i-1,1},(f_{i-1,0}+1)[a_i=1])。偶数位全为 1 的情况类似，则只需要满足这两种情况中存在一组 \max(f_{n,0},f_{n,1})\ge k 就符合条件。时间复杂度 O(n\log n)。