AT_arc165_d [ARC165D] Substring Comparison
考虑字典序的性质。
我们维护当前的 \(a_i,c_i\) 表示判断 \(a_i\) 是否 \(<c_i\)，连边。
tarjan 判环，如果是一个环，说明环上所有点都相等。
注意，我们连边是对两个点的环进行连边。
对于一个限制，如果当前的 \(a_i,c_i\) 都在环上，即前缀都相等，那么 \(a_i,c_i\) 都往下跳一位，说明我们判断下一位的关系。
最后跑完某个区间判断有无解即可。
如果 tarjan 时没有新的环合并，那么结束。
AT_arc165_e [ARC165E] Random Isolation
什么神仙。
将期望转到局面上。
发现期望相当于每个还可以操作的局面出现的概率之和。
于是我们找到局面，算概率即可。
找到树上一个大小为 \(a\) 的子图，满足 \(a>k\)，如果有 \(b\) 个之外的点与之相连。
我们考虑将操作的序列看成排列，那么出现这种局面的概率为 \(\frac{a!b!}{(a+b)!}\)，因为这 \(b\) 个数都得在 \(a\) 的前面，相对关系确定了。
然后树上背包转移即可，令 \(f_{u,i,j}\) 表示只考虑 \(u\) 的子树内的点，\(u\) 在子树内的联通块大小为 \(i\)，与之相连的点有 \(j\) 个的方案数。
AT_arc108_f [ARC108F] Paint Tree
发现同颜色最远点对一定有一点在直径 \(S\) 上。
这下找到直径，算每个点到直径的两种距离。
然后枚举最远点对长度 \(d\)，根据两种距离跟 \(d\) 的大小关系，我们可以知道一个点选的方案数。
然后我们考虑容斥。
记答案为 \(\sum w_if_i\) 的形式，表示最远点对为 \(w_i\) 的方案数为 \(f_i\)。
对于一个 \(x\)，我们计算 \(g(x)=\sum [w_i> x]f_i\)，则答案为 \(\sum\limits_{x=0}^{S-1} g(x)\)。
我们钦定直径的颜色不同。
记 \(mn=\max(\min(d1_i,d2_i))\)，即最远点对的最小值。
对于 \(x\in [0,mn)\)，\(g(x)=2^n\)。
对于 \(x\in[mn, S)\)，\(g(x)=2^n -\sum [w_i\le x]f_i\)，减去的就是最远点对 \(\le x\) 的方案数。
对于点 \(i\)，如果它满足 \(\max(d1_i,d2_i)\le x\)，则它两种颜色都可以染；否则它只能染一种。记满足前者条件的点有 \(cnt\) 个，则 \(\sum[w_i\le x]f_i=2^{cnt + 1}\)，还有对直径颜色的分配。
P9129 [USACO23FEB] Piling Papers G
差分区间。
位数 \(\leq len\) 的容易算。
考虑反着来，枚举右端点 \(r\)，往左推，那么每次就是在前缀的最后和后缀的最前加数，分别维护左右侧和 \(x\) 的大小关系就可以转移了。
倒着与正着相比，优势是正着得根据一个确定点来判断大小，而倒着的话，整个序列的形态是固定的。
具体，设 \(f_{l,x,y,s,t}\) 表示左端点推到 \(l\)，左侧与 \(x\) 的 \([l,r]\) 相比 \(<\)，\(=\)，\(>\)，右侧同理，的方案数。
做完了。
P9130 [USACO23FEB] Hungry Cow P
考虑每次修改的都是不同的位置，对于一次修改 \(a_x=y\)，相当于区间覆盖 \([i,k]\)，满足这次修改前 \([i,k]\) 中的空位置为 \(j\)，简单的线段树二分。
对于同一位置的多次修改，我们要让前一次修改对后一次修改没有影响， 就对时间进行线段树分治即可。
发现不好维护撤销，我们就可持久化动态开点线段树。
时间复杂度 \(\mathcal O(n\log n\log V )\)。