2026.10.25 衡中集训
ACM 被固定思维坑麻了。学长出的题下手就是狠。
ACM 赛题
A. 1！2！3！
场上时间差了点，没调出来。
我的做法：
修改操作就是将 1 的个数变为 2 的个数，2 的个数变为 3 的个数，3 的个数变为 1 的个数。这儿用线段树维护节点 1/2/3 的个数还是好做的。
对于查询操作，思考一次子区间操作对答案的变化，在于两个二进制位的异或。例如 3->1，就是第二位变化一次。同时，还有连着的变化，如 2->3 且 3->1，此时第一位和第二位都变化了。
可以证明，每次最优变化的最小子区间长度不超过 2：单个的 1/2/3 变化自然最小长度是 1，而我们发现，两个连续的数的效果等同于那个没有出现的数。使用两个连续的数而不是单数的原因当然是单数没有出现。如果两数之间还有别的数，一定是那个没有出现的数，我们会使用单个的数以替代两个数。
区间修改使用懒标记。由于修改最终是个环，能绕回来，所以懒标记 + 1 再取模 3 就可以了，当然懒标记处理的时候复杂度是对的。
实现上，我在每个节点上维护了 cnt01,cnt10,cnt11,lef,rig,cnt0110,cnt0111,cnt1001,cnt1011,cnt1101,cnt1110,lazy，虽然很多，但是每个的意义和用途都是很明确且单一的。
出题人做法：
与我的做法不同的是，他维护的是集合。发现我的做法中 cnt1101 和 cnt0111 实际上是一样的，所以维护取值的集合可以使线段树上挂的东西少一点。
验题人做法：
数的集合大小大于等于 2 时，实际询问时的区间修改所异或的值可以是 0/1/2/3。如果两个数都凑不全自然看看唯一有的那个数有没有用。所以维护连续段是可以免去的，取而代之的是从有的数的集合的角度出发来考虑问题。
很 atcoder，联想到 atcoder 的那场线段树训练赛。
B. RGB 色彩空间
无言。
C. 圣女？骑士？沙拉！
可以把问题转化到放点权上，祖先的点权小于等于自己的点权。
我一开始想这个东西重了怎么办巴拉巴拉的，是不是还得容斥。但我们从父节点的角度考虑，此时只需要把每个子树来的点看成一个颜色，不同子树来的不同点看成不同颜色，求方案数就好。这样的角度好处在于我根本不用管值到底取了多少，反正同一颜色内一定是原来的顺序，不同颜色不相干，所以求方案数也是对的。
很 codeforces。
D. 辉夜姬保卫战
What can I say?
很容易想到距离这个东西要变成 dep_u + dep_v - 2 dep_lca(u,v)，前面两个东西当然好处理，后面这个就不好处理了。
一个关键的转化是，将从根到 u 的路径上加 1，后面 dep_lca(u,v) 就是从根到 v 的路径上的值之和。这样把必须 n^2 枚举的东西给变成求和的很好优化的东西了。
于是我们可以树链剖分！复杂度双 log。
然而我们注意到这是随机的树，树高为 O(log n)，所以暴力跳即可。
还有高手，神秘点分树 / toptree 在所有情况下都是 O(n logn) 的。
场上转化没想到，实际上后面的实现是想到了的。
E. 呼啸山庄
神秘题目。
在最差情况下，所以将 b 和 c 考虑为一种群体。在 a <= b+c 时，若 b+c 都指向同一个假位置，主人公找不到正主，只能当渣男。
否则，询问到 a 的次数为 b+c+1 次时，指向正主的位置一定大于其他位置，所以可以确定。
特殊处理的，当 a+b+c=1 时，答案应为 0。
F. zyz 的狼人杀
无言。
G. 炼金术师与人鱼姬
特殊情况下，所有值都不同，显然是个一般的 LIS 问题。
好吧这题有点困难，请求学长 / 学姐再支援一下。
H. @KingGojianOfYue 突破
临项交换法。注意到交换 i 和 j 的位置对于剩下的位置的答案贡献没有影响。
设在此之前，时间已经过去了 x 时间。
若 i 在 j 之前，它们的贡献是 a_i \times x + a_j \times (x + b_i)，反之同理。
将共同项消去，只剩 a_ib_j 和 a_jb_i，根据这个排序即可。这样其实是比按照 a_i/b_i 排序要更好一点（？
int128！！！
I. 植物大战僵尸
非常快啊，我观察到这个本质是排序后将数组分为若干段，段的贡献为 a_i + len^4。
这样 DP 十分的好写。dp_i 表示到第 i 段，段已结尾的最小代价，dp[i] = a[i] + min(dp[j] + (i-j)^4)。
这坨 4 方难以入手。赛时去想贪心双指针了。
注意到 200^4 > 很大的数，所以每个 i 的转移 j 不超过 200 个。
J. 我会卡特兰数！
注意到 4892 是卡特兰数第 9 项。
但是我赛时做法更吃操作些。