题目随记
https://47.94.97.204/contest/1694/problem/4
题目中直接给出了 $\frac a2$ 时间复杂度 $\log V$ 的提示太明显了，直接上套路即可。
没有做出来的究极无敌逆天简单题
CF1841C Ranom Numbers
https://www.luogu.com.cn/problem/CF1841C
本题关键：发现性质优化暴力。
最近增量题做的比较多，看到这个题马上就去考虑增量，然后一直讨论没有讨论出来。
实际上有用的字符就只有开头和结尾的，把他们找出来之后暴力跑就行了。
好题
P8163 [JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)
https://www.luogu.com.cn/problem/P8163
这个题如果同时思考 $A_j < B_j$ 和 $A_j > B_j$ 脑子是会爆炸的，对于这种有操作会莫名其妙夹在在一起的题，应当考虑化简问题，只考虑其中一种做法，并尝试推广到全局。也就是非常有启发性的子任务 $5$。
尝试只考虑 $A_j < B_j$ 的问题该如何处理，我们可以使用 multiset 维护出对于每个点，其只乘坐一次列车能够到达最远的点是哪一个 $rii$；那么对于每一次询问，初始时 $[l, r] = [s, s]$，做一次列车相当都对 $r$ 执行如下操作：$r \gets \max{i\in[l, r]} ri_i$，需要用到 ST 表，如果暴力更新 $r$ 那么复杂度是 $O(qn\log n)$，考虑优化，有一个很显然的想法是使用倍增 $ri(i, j)$ 代表点 $j$ 走了 $2^i$ 步最远能够到达的右端点，按照平时 $ri(i, j) = ri(i-1,ri(i-1,j))$ 转移是不行的，因为 $[j, ri(i - 1, j)]$ 中所有的值都可能影响 $ri(i, j)$ 的取值，所以需要用到 ST 表进行区间查询最大值时间复杂度 $O(n \log^2 n) - O(n \log n)$。
回到原问题，本质上我们是要依次扩展区间 $[l, r]$，对于 $A_j >B_j$ 的情况和刚才的区别在于倍增中区间查询的左端点不是不变的了，令 $le(i, j)$ 代表点 $j$，最少转 $2^j$ 次车能够到达的最远左端点，转移时查询的区间变为 $[le(i - 1, j), ri(i - 1, j)]$，本质上还是对于一个区间进行倍增转移，与子任务 $5$ 的做法没有本质区别。
P9527 [JOISC2022] 洒水器
https://www.luogu.com.cn/problem/P9527
注意到 $D \le 40$ 有一个很显然的思路，对于每一次修改操作，暴力向上跳 $k$ 级祖先，然后利用类似于中途相遇的思想去统计问题，定义 $f(u, d)$ 为离节点 $u$ 距离 $= d$ 的操作乘积。但是这样子会算重，在计数问题中算重有三种解决方法：
- 换做法，考虑暴力维护 $g(u, d, v)$ 为 $f(u, d)$ 抛去子树 $v$ 的答案，时间复杂度是 $O(qd^2)$ 无法通过，我就卡在了这一步。
- 容斥，这道题的答案不满足可减性（模数不是质数）。
- 钦定在某一个位置计算贡献（往往是端点）。
第三点是最容易忽视的一点，其实这个问题在做区间计数问题出现的次数比较多，在这类问题中，往往会钦定区间在右端点的位置进行转移，这便是第三点的体现。
回到这个问题，对于两个点 $u$ 和 $v$，他们会在 $lca(u, v)$ 处开始重复计算贡献，这是端点之一。令这一次操作的距离为 $d$，$a$ 是 $u$ 的若干级祖先。当 $dis(a, u) + dis(a, v) = d - 1$ 或 $dis(a, u) + dis(a, v) = d$ 时是另一个端点。显然选取前者对我们没有任何好处，考虑选择后者。
现在的问题便可以做了，每次修改操作，在对应的节点上记录一下对应的 $d - 1 - dis(a, u)$，这样对于每个 $dis(a, v)$ 快速查就可以了。
P6345 [CCO2017] 接雨滴
https://www.luogu.com.cn/problem/P6345
考虑拆贡献，考虑一个位置的贡献是什么，令 $pre_i$ 为前 $i$ 个数字中，大于 $a_i$ 且最大的数；令 $suf_i$ 为 $i \sim n$ 中大于 $a_i$ 且最大的数，如果不存在这样的数则值为 $0$，那么 $f(b) = \sum min(suf_i, pre_i) - b_i$。
此时便可以考虑区间 DP 还要配上可行性背包，$f_{i, l, r, k}$ 代表考虑了前 $i$ 大的数，已经被填过的区间为 $[l, r]$，值 $k$ 能否被构成，时间复杂度 $O(\frac{n^4v}w)$，显然记录具体是哪一个区间是非常 trivial 的，我们没有必要这样，卡在了这里不知道干嘛了。
枚举区间很显然是不能够给我们带来任何好处的，考虑 $f_{i, j, k}$，前 $i$ 大的数，已经填了长度为 $j$ 的区间，$k$ 能否被构成，转移是非常普通的，时间复杂度为 $O(\frac{n^4v}w)$。转移是从 $f_{i - 1, j - d, k - d \times a_i}$ 转移到 $f_{i, j, k}$。但这里还能够将每次枚举的转移常数转化为完全背包问题，也就是我们每次会枚举的 $d$，实际上可以看成由 $f_{i - 1, j - 1, k - a_i}$ 转移到 $f_{i, j, k}$，的完全背包，省略了枚举 $d$，时间复杂度为 $O(\frac{n^3 v}w)$。
当然对于每一个相同的 $a_i$ 只需要转移一次，时间复杂度可以做到 $O(\frac{n^2v^2}w)$，都需要用到 bitset 优化。
P6345 [CCO2017] 接雨滴
https://www.luogu.com.cn/problem/P6345
考虑拆贡献，考虑一个位置的贡献是什么，令 $pre_i$ 为前 $i$ 个数字中，大于 $a_i$ 且最大的数；令 $suf_i$ 为 $i \sim n$ 中大于 $a_i$ 且最大的数，如果不存在这样的数则值为 $0$，那么 $f(b) = \sum min(suf_i, pre_i) - b_i$。
此时便可以考虑区间 DP 还要配上可行性背包，$f_{i, l, r, k}$ 代表考虑了前 $i$ 大的数，已经被填过的区间为 $[l, r]$，值 $k$ 能否被构成，时间复杂度 $O(\frac{n^4v}w)$，显然记录具体是哪一个区间是非常 trivial 的，我们没有必要这样，卡在了这里不知道干嘛了。
枚举区间很显然是不能够给我们带来任何好处的，考虑 $f_{i, j, k}$，前 $i$ 大的数，已经填了长度为 $j$ 的区间，$k$ 能否被构成，转移是非常普通的，时间复杂度为 $O(\frac{n^4v}w)$。转移是从 $f_{i - 1, j - d, k - d \times a_i}$ 转移到 $f_{i, j, k}$。但这里还能够将每次枚举的转移常数转化为完全背包问题，也就是我们每次会枚举的 $d$，实际上可以看成由 $f_{i - 1, j - 1, k - a_i}$ 转移到 $f_{i, j, k}$，的完全背包，省略了枚举 $d$，时间复杂度为 $O(\frac{n^3 v}w)$。
当然对于每一个相同的 $a_i$ 只需要转移一次，时间复杂度可以做到 $O(\frac{n^2v^2}w)$，都需要用到 bitset 优化。
CF1845E Boxes and Balls
https://www.luogu.com.cn/problem/CF1845E
首先如果移动 $k$ 次能够达成某种状态，那么 $k + 2$ 次也可以。
对于这种给定若干操作计数问题可以讨论最终状态的合法性。
用 $a$ 描述状态，$a_1 < a_2 < \cdots < a_{|a|}$ 描了所有有球的位置，令 $a$ 表示初始状态，$b$ 描述结束状态，则有 $|a| = |b|$
考虑 $a$ 变为 $b$ 的最小操作步数，则 $f(b) = \sum |a_i - b_i|$，如果有解则必然满足 $2 \mid k - f(b)$。
定义 $f_{i, j, k}$ 代表前 $i$ 个位置有 $j$ 个 $1$ 且 $f(b) = k$ 时的方案数是多少，可以从 $f_{i, j, k}$ 转移到 $f_{i + 1, j + 1, k + |i + 1 -b_{j}|}$。
直接做是 $O(n^3)$ 的，但是我最开始自己做的时候以为这样的状态会漏掉东西，主要是没有考虑到 $f(b)$ 的值其实能够帮助我们确定 $b$，再加之并没有想到操作次数最小这个东西。
每次都枚举一堆 $j$ 是没有意义的，如果想把 $x$ 个 $1$ 从 $i$ 挪到 $i + 1$，至少需要 $x^2$ 步，所以只需要枚举 $\sqrt k$ 这个两级就行。有人认为这种问题是关于不降序列对应位置距离之和，有经典套路：在每个间隔处统计答案。也可以说是每个间隔的花费。
124oj3303 小 T 与灵石（stone）
http://124.221.194.184/contest/135/problem/3033
此题关键在于：将询问的无效信息删去，只保留必要信息。
虽然询问给定了大小为 $k$ 的点集，实际上很多的点都是无用的，只需要考虑相聚最远的两个点，也就是这个点集的“直径”。
设直径的两个端点为 $x$ 和 $y$，设 $x$ 的深度大于 $y$，直径中点为 $m$，则 $m$ 把树分成了两个部分，其一为 $m$ 的子树内，子树内的点到 $x$ 的距离就是答案，反之亦然。子树内和子树外在 $dfn$ 上一定是一段区间，因为在计算 $dis$ 的时候会有 LCA 的影响非常麻烦，考虑点分治配上优先队列，维护这一过程。
其实没有必要，对于一个直径，$max(dis(u, x), dis(u, v)) = \frac {len}2 + dis(u, m)$，可以用经典的的树形 DP 解决问题。
CF1661F Teleporters
https://www.luogu.com.cn/problem/CF1661F
这个问题关键在于：从答案的增量考虑问题。
结论1： 一定是在相邻的两个传送机平均分配新的传送机。
社 $f(x)$ 代表相邻的两个传送机中插入 $x$ 个新的传送机的价值，$g(x) = f(x) - f(x + 1)$，人话 $g(x)$ 是 $f(x)$ 的增量，可以证明 $g(x)$ 是单调递增的。
我们可以用一个优先队列记录每个相邻的传送机带来的贡献，配合上二分，但这样做时间复杂度是有问题的。
考虑我们用优先队列解决问题的本质，他一定会先选择减量大的相邻的传送机，且选过的 $g(x)$ 一定不小于没有选定的 $g(x)$，满足单调性，这启示我们二分减量。
对于每一个相邻的传送机，我们都可以二分出 $g(x)$，这便完成了 check，本题完结。
时间复杂度 $O(n \log^2 n)$。
P3589 [POI2015] KUR
https://www.luogu.com.cn/problem/P3589
此题关键之处在于：将出现次数转化为可能出现的位置数量，剩下的内容比较套路。
不妨从特殊情况开始思考。
若 $m = 1$ 时，答案是显然的；若 $m = 2$，我们可以将满足 $s_i = t_1$ 的位置标记出来，接着再从标记过的位置中重新标记找到 $s_{i + 1} = t_2$，最终标记的数量便是我们需要的答案。对于 $m$ 更大的情况，依然可以这样处理。
现在问题转化为：给定若干个区间，求这些区间的交。由于 $n$ 是 $10^9$ 级别的，所以需要用离散化和差分，实际上这样子实现起来比较复杂，可以转而维护不合法区间的并。
现在的问题是如何求出这些区间。
设 $t$ 在 $s$ 中匹配的位置为 $i$，有 $t_{x + 1} = s_{i + x}$，下标从 $0$ 开始。
- 当 $t_{x + 1} = 0$ 时，有 $0 \le (ai + ax + b) \bmod n < p$，化简可得 $-ax-b\leq ai <p-ax-b$。
- 否则，有 $p \le (ai + ax + b) \bmod n < n$，化简可得 $p - ax - b \le ai < n - ax - b$。
由于是在模 $n$ 意义下，可能会出现类似 $p - ax - b > n - ax - b$ 的情况，此时 $ai$ 的取值范围为 $[p - ax - b, n - 1] + [0, n - ax - b)$，对于$t_{x + 1} = 0$ 同理。
蠢蠢的笔者看了别的题解自己推式子的时候把 $a$ 除了过去，然后发现以 $i$ 为下标的序列构成的区间根本不是连续的！思考了半天，其实不除过去就行了，因为当 $\gcd(a, n) = 1$ 时，$ai \bmod n$ 与 $i \in[0, n - 1]$ 的取值一一对应，故我们只需要统计有多少个 $ai$ 满足条件即可。
当然如果你这样统计完之后你会发现你算出来的结果比标准答案要大，这是由于我们把 $[n - m + 1, n - 1]$ 这一坨合法的答案统计进去了，减掉即可。
代办
http://124.221.194.184/contest/135/problem/3038 、 https://www.luogu.com.cn/problem/AT\_abc134\_f 绝对值和拆贡献。