推结论力低下的问题直到高二赛季的 NOIP 才显露出来。
或许这就是命运吧。
T1
求出每个字符串能够调整得到的字典序最大和字典序最小的字符串，只需要判断一个串对应的最小串是否比其它所有串的最大串小即可。可以维护最大串的最小值和次小值。
T2
动态维护 \(pos_i\) 表示 \(i\) 位置和最初的哪个数相等，对 T,F,U 单独建点。到最后扩展域并查集合并一下 \(i\) 和 \(pos_i\) 即可，如果存在矛盾说明集合一定都是 U，计入答案。
T3
想了三天才会/cf
首先可以平方 DP：设 \(f_{i,j}\) 表示当前两个序列的末尾元素分别是 \(i,j\)，是否可行。那么转移为：
\[f_{i,j}=(f_{i,j-1}\lor f_{i-1,j}\lor f_{i-1,j-1})\land A_{i,j} \]这相当于询问矩阵 \(A_{i,j}=[a_i<b_j]\) 中 \((1,1)\) 和 \((n,m)\) 是否八连通。
首先说明一件事情，就是第三种转移并没有用。这是因为如果 \([a_i<b_j]\land [a_{i+1}<b_{j+1}]\) 成立，那么 \(a_{i+1}<b_j\) 和 \(a_i<b_{j+1}\) 必有一者成立，所以这种转移没用。
尝试观察路径会怎么走：假设钦定是向上走，那么直觉是我们希望跳到一个 \(b_j\) 尽可能大的地方转向。
然而这么做会存在一个问题，也就是用当前的 \(a_i\) 能走到 \(b_j\) 的最大值位置之后，跳到的下一个 \(a_{i'}\) 未必能够覆盖 \(j+1\) 之后 \(a_i\) 能跳到的位置。所以我们尝试把跳跃过程分成两个阶段：如果保证存在 \(a_{i'}\) 比 \(a_i\) 更小，那么直接跳是不存在问题的，称之为阶段一；否则 \(a_i\) 和 \(b_j\) 均为 \((i,j)\) 能跳到的位置的最小值和最大值，这个称为阶段二。我们发现：\((i,j)\) 能一步跳到的横坐标最大的位置 \(x\) 和纵坐标最大的位置 \(y\) 一定满足 \(x=n,y=m\)。这是因为如果不存在的话，\((x,j)\) 到 \((i,y)\) 的一条右上折线一定都是 \(0\)，这样我们一定不能到达 \((n,m)\)。所以 \((n,j)\) 到 \((i,m)\) 的一条左下折线一定都是 \(1\)。
考虑如果解决阶段二的跳跃。显然，我们需要保证跳到的点都满足上面的条件。假设钦定向上跳，此时我们希望跳到的位置越远越好，这是因为如果不跳到最远的点，剩余的所有方案一定会经过最远点对应的纵坐标，因为有左下折线均为 \(1\) 的限制，我们可以调整证明。
于是我们确定了两个阶段的方案。事实上没必要真的这么写，特殊性质提醒我们，如果直接找到最值的位置，则可以把问题从中间拆成两个阶段二问题，于是直接模拟即可。可以实现到 \(\mathcal{O}(nq)\)。
T4
离散化，把 \(r\) 和 \(l-1\) 看作特殊点，设 \(f_i\) 表示只考虑 \([1,i]\) 段，且钦定第 \(i\) 段留空的最大贡献。那么转移方程是：
\[f_i=\min_j\{ f_j+w(j+1,i-1)-(p_i-p_{j+1})d\} \]其中 \(w(j,i)\) 表示区间 \([j,i]\) 覆盖的所有区间的贡献和，\(p_i\) 表示第 \(i\) 段的起点。利用线段树容易优化至 \(\mathcal{O}(n\log n)\)。
标签：位置,NOIP,跳到,阶段,2023,我们,折线 From： https://www.cnblogs.com/yllcm/p/17844250.html