水镜
先考虑如何判定一个区间 \([l,r]\) 是否合法。
首先肯定存在一个分割点 \(mid\)，使得 \([l,mid]\) 取 \(\min(h_i,2L-h_i)\)，\((mid,r]\) 取 \(\max(h_i,2L-h_i)\)。
因此，记 \(p_i=\max(h_i,2L-h_i)\)，则 \(p_i\) 需要先不升，再不降，并且只能在转弯处有至多一对相等。
考虑其反面，也即不存在 \(p_{i-1}\leq p_i\geq p_{i+1}\)。对于每个 \(i\)，这会导出一个限制，为 \(L\notin[l,r]\)，则判定一个区间是否合法只需要判定所有限制的并是否为全集即可。
又因为答案具有单调性，所以双指针即可，判定全集有一万种方法，时间复杂度 \(O(n\log n)\)。
线段树
记线段树 \(i\) 点的区间为 \([L_i,R_i)\)。
首先需要做一个转化：对于线段树上第 \(i\) 个点，如果我们知道其权值，就将 \(L_i\) 与 \(R_i\) 之间连一条边，那么 \([l_i,r_i)\) 的权值可以求出充要于 \(l_i\) 与 \(r_i\) 联通。
把线段树这个图放到平面图，会发现这是一个三角剖分类似物，因此对于第 \(i\) 个点，会有两种情况：
- \(L_i\) 与 \(R_i\) 联通，并且子树内的联通已经处理好了，子树内到子树外的联通要求都和 \(L_i\) 联通了。
- \(L_i\) 与 \(R_i\) 不联通，并且存在一个 \(j\)，使得子树内所有没有跨过 \(j\) 的联通要求都满足了，跨过 \(j\) 的联通要求都一端和 \(L_i\) 联通，一端和 \(R_i\) 联通。
则我们将第一种记作 \(f_i\)，第二种记作 \(dp_{i,j}\)。
\(f\) 与 \(f\) 之间的转移是平凡的。
\(f\) 与 \(dp_i\) 的转移不会改变 \(j\)，因此是一个整体乘法。
\(dp_{u,x}\) 与 \(dp_{v,y}\) 的转移需要要求跨过 \(x,y\) 的限制相同，也就是，\((x,y]\) 的要求都在 \(mid_i\) 满足了。这个可以用 xor-hash 处理出等价类，然后在等价类之间转移。
最后在 \(i\) 点的 \(dp_i\) 还要整体转移到 \(f_i\)。
上述过程可以用线段树合并维护，时间复杂度 \(O(n\log n)\)。
众生之门
首先任何一棵树都可以构造出一个排列，满足相邻两个点距离 \(\leq 3\)，因此答案 \(\leq 3\)，并且因为奇偶性是确定的，所以答案的最后一位是确定的。因此我们只需要确定答案的倒数第二位是啥就行了。
然后发现，除了菊花和 \(n\) 比较小的情况，最后的答案都是 \(\leq 1\) 的。
但是怎么构造呢？答案是直接随机（。因为你感受一下，你随机一个排列，答案是均匀的，因此每次随机交换两个位置，然后计算新的贡献即可。
多方计算
首先我们有一个 \(n+m+\log n\) 的做法：在第 \(t\) 个时间将所有第 \(x\) 个人的第 \(y\) 位满足 \(x+y+1=t\) 传到下一个人，并把这一位清空，下一个人将这个值加到对应位置上并进位。这样最多需要增加 \(\log n\) 位，可以获得 \(49\) 分。
这个做法刚开始的时间非常浪费，后面的点都没有传递信息。我们考虑让后面的点从 \(\log n\) 位开始传递信息，传递一个三角形掉，这样前面的进位就只有 \(\log \log n\) 个了，就可以做到 \(n+m+\log \log n\)。
这样会比限制多一步，我们只需要让开始的位从略小于 \(\log n\) 的位置开始。真正限制开始位置的是这一次加法的进位数量，我们将后面的三角形改成对很多平行四边形同时做加法，就可以刚好进这个限制。
投票游戏
首先我们可以求出 \(f_i\) 表示 \(i\) 被票出时候 \(i\) 有几票，这样只需要比较 \((f_c,c)\) 和 \((f_d,d)\) 的大小即可。
首先考虑假设 \(i\) 的儿子的 \(f\) 都知道是啥了，\(f_i\) 怎么求。维护一个变量 \(x=a_i+\sum\limits_{j\in son_i}b_j\)， 当票数降到某个 \(f_j\) 的时候，将 \(x\) 减去 \(b_j\)。当 \(x\) 第一次和票数相同的时候就是 \(f_i\) 的值。这个值可以维护线段树并在线段树上二分快速得到。这样就可以做随机树和菊花的情况。
然后一个自然的想法是轻重链剖分，并在重链上维护一些信息。考虑 \(i\) 的重儿子 \(j\)，记 \(i\) 去掉 \(j\) 之后的答案为 \(g_i\)，则若 \(f_j<g_i\)，则 \(f_i=g_i\)，否则说明 \(b_j\) 最终一定会被去除，则在线段树上改一下初始值之后再二分出另一种答案即可。
这样我们每个点的答案可以用一个函数表示：
\[f(t)=\begin{cases} A && t<x\\ B && t\geq x \end{cases} \]这显然可以线段树快速求一条链上的答案，然后轻边暴力，这个题就做完了，时间复杂度 \(O(n\log n\log V)\)，如果维护儿子的地方写平衡树就可以做到 \(O(n\log ^2n)\)。
字符串游戏
记 \(occ(i,j)\) 表示 \(s[i,j]\) 在 \(s[i,n]\) 中出现次数。
记 \(dp_i\) 表示 \(s[i,n]\) 的答案，显然有 dp 是 \(f_i=\max\limits_{j=i+1}^{n}{occ(i,j-1)-f_j}\)。
这个 dp 是 \(O(n^2)\) 的，非常不牛。为了优化这个 dp，我们需要对这个 dp 观察一些性质。
一个比较容易发现的性质是，如果 \(i<j\) 且 \(f_i\leq f_j\)，则从 \(i\) 转移一定不会比从 \(j\) 转移更优，因为 \(occ(x,i)\geq occ(x,j)\)，所以我们只需要保留 \(f_i\) 的前缀最小值即可。
但这是不够的。我们还可以注意到，如果在某次转移中，\(i\) 的最优转移点是 \(p_i\)，则 \(p_i\) 之前的转移点都没有用了。这是因为对于两个 \(occ(x,i),occ(x,j),i<j\)，在 \(x\) 减一的过程中，\(occ(x,i)\) 的减小量 $\geq $ \(occ(x,j)\) 的减小量。
这样就可以决策单调性，但是复杂度是两个 log 的，过不了。
我们尝试维护一个单调栈，栈内满足 \(f\) 单调递减。每次拿栈顶转移到 \(i\)，然后判断 \(f_i\) 是否小于栈顶，如果小于就把栈顶弹了，否则退出。
这个做法的正确性在于，我们做完之后，记栈顶为 \(x\)，一个非栈顶为 \(y\)，需要证明 \(x\) 对 \(i\) 的转移不劣于所有 \(y\) 对 \(i\) 的转移。
反证，假设 \(f_i=occ(i,y-1)-f_y\)，则有 \(f_i\leq occ(x,y-1)-f_y=f_x<f_i\)，矛盾。因此 \(f_i\) 转移完备。
所以我们只需要支持求 \(occ\) 即可，这个可以倍增+bit 实现，时间复杂度 \(O(n\log n)\)。
标签：联通,log,线段,答案,CTS2024,occ,dp From： https://www.cnblogs.com/275307894a/p/18408001