260901 - 260913
AT_arc068_d [ARC068F] Solitaire
\(1\) 之前的东西是一个 LIS 不超过 \(2\) 的序列，并且存在一个 LDS 划分使得没出现过的 \(n-k\) 个数可以拼在其中一个 LDS 之后。显然应该把下降链作为一个 LDS，剩下的作为另一个，简单使用前缀和优化可以做到 \(O(n^2)\)。
qoj10298 公交
一段路不会走超过 \(3\) 次，分析可知只有一种结构：343212345432（或左右对称）。枚举 \(4\) 的位置，设 \(mn\) 表示 \(4\) 右边指向左边的路线中，最靠左的终点。贡献就是 \(2dis(2,4)+R-mn\)，可以通过从右往左扫描线处理。
qoj9438 Two Box
把 \(\le x\) 的限制拿出来，序列被划分成了一些区间，要求每个区间内 \(>x\) 的数都出现偶数次（除了最后没有限制时的最后一段）。注意到 \(x\) 从小到大，这些区间形成一棵树，我们从下往上填数，第 \(x\) 层填 \(x+1\)。状态记录剩余位置数量，转移形如一个只有偶数的点值平移，本质是 \(\frac{g(x-1)+g(x+1)}{2}\)。用线段树维护 \(g(-m)\sim g(m)\) 的点值即可，复杂度 \(O((n+q)m^2\log n)\)。
qoj837 Giant Penguin
任取一棵生成树，进行点分治，跨过分治中心的非树边只有最多 \(10\) 条，以非树边的端点和分治中心最多 \(11\) 个点为起点进行 bfs，修改时在点分树的每个祖先上更新这些点的距离即可。
qoj967 Rectangle Painting
对每个数维护其没出现过的位置构成的段，然后把段扔到线段树上，可以维护区间最高的最低点，用线段树套 set，复杂度 \(O(n\log^2n)\)。
P13342 [EGOI 2025] Wind Turbines / 风力涡轮机
就是要求连接 \([l,r]\) 所有点之后的最小生成树，那么一条边会被保留当且仅当 kruskal 重构树上两棵子树至少有一棵不包含 \([l,r]\) 的任何节点，正难则反，根据启发式合并支配对只有 \(O(n\log n)\) 个，于是二维数点即可。
uoj1005【UR #32】王之钦定
极大合法区间形如一些相交的区间，\(i\) 和 \(i+1\) 有交但和 \(i+2\) 无交。每次新加一段区间的时候，只关心和上一段的相交部分，因此设状态 \(f_{j,i,c}\) 表示最后一个区间右端点为 \(i\)，和下一个区间相交部分的左端点为 \(j+1\)，\((j,i]\) 颜色全部为 \(c\) 时的最大价值。考虑转移，\(j'=i\) 需要单独处理，此时固定 \(j'\) 和 \(i\) 之后可以对 \(i'\) 和 \(j\) 使用斜率优化，复杂度 \(O(n^2m)\)。否则分步转移，\(f_{j,i}\to g_{j,j'}\to f_{j',i'}\)，需要满足 \(\{c_i,c_{i+1}\}=\{c_{j'},c_{j'+1}\}\)，由最优性 \(c_{i+1}\) 和 \(c_{j'}\) 没有改变，因此只用记另外一个，中间每个元素的贡献也可以用 \(m\times m\) 的辅助数组在 \(O(m)\) 的复杂度内处理。复杂度 \(O(n^2m)\)。
AT_arc227_f [ARC227F] Erase and Raise
先把交叉的操作都调整成包含，然后从里往外操作，这样就只有对两个 \(0\) 的操作了。然后从上往下扫描值域，dp 记录操作次数和连续段数量，由于不同连续段使用的操作是独立的，因此连续段数没法超过 \(O(\sqrt n)\)。于是直接转移就是 \(O(n\sqrt n)\) 的。
qoj1173 Knowledge Is...
感觉很难想到。把区间按左端点排序，用两个 set 分别维护还未匹配的左侧区间，以及已经匹配的右侧区间，每次加入时先尝试匹配第一个 set 中的区间，尽量匹配左端点靠右的区间；若未匹配，则尝试取代第二个 set 中右端点最靠右的区间。
P16365 [OOI 2026] Tasks from Sasha [qoj link]
感觉很典啊。如果点数不太大，可以记 \(f_{u,i}\) 表示子树内有 \(i\) 个人参加外子树的活动，转移形如把子树卷起来然后点值平移，于是自然的想到维护点值。需要去除无人来参加活动，和参加活动的人全部来自于一棵子树的情况，这些都是可以在 \(O(n^2)\) 内解决的。
考虑如何在虚树上处理，边上挂的子树都是好处理的，如果一个活动地点下面挂了一堆不在虚树内的子树，总方案数和无人参加都还容易计算；而对于 \(\operatorname{lca}\ne u\) 的情况，需要对这些子树的大小分治：若 \(sz\ge k\) 则直接 \(O(k)\) 暴力算贡献就是对的；否则我们把大小相同的子树放一起处理，复杂度可以分析到 \(O(n^{1/2}k^{2/3})\)，总共就是 \(O(n\log n+k^2+n^{1/2}k^{2/3})\)，应该需要光速幂去掉 \(\log\)。
P15952 [ICPC 2018 Jakarta R] Rotating Gears
图上删边是可以做的。考虑树的性质，每次操作时首先找到本连通块的根 \(x\)，那么节点 \(y\) 属于本连通块充要于：\(y\) 属于 \(x\) 的子树内，且 \(y\) 根链上断点数目等于 \(x\) 的。不难发现该断点数目等于子树内的最小值，于是对最小值打 tag 即可。不想动脑子可以用倍增 \(\log^2\) 找根，也可以用线段树上二分找。
P9530 [JOIST 2022] 鱼 2 / Fish 2
P8375 [APIO2022] 游戏
260904 模拟赛 D
给定一个序列 \(a\) 和常数 \(X\)，每轮行动当前玩家选择一个非空的区间，将其中的 \(a_i\gets X-a_i\)，Alice 先手，希望最终序列的和尽可能大，Bob 反之。给定游戏轮数 \(k\)，问最终序列的和。
\(n\le 2\times 10^5\)
首先需要注意到 \(k=3\) 不会比 \(k=1\) 更优，也不会比 \(k=1\) 更劣，因此只需解决 \(k=1\) 和 \(k=2\)，前者是最大子段和。
考虑 \(k=2\)，Alice 需要选择一个区间，最小化 Bob 的最优决策。考虑对 Alice 的区间分治，Bob 的决策可以表示成和区间左右两端点有关的 \(\max(L1_i+R1_j,L2_i+R2_j,L3_i+R3_j)\)，钦定其中一个为 \(\max\) 并最小化它，化简后是一个二维的约束，于是跑二维数点，总共需要跑三遍。时间复杂度 \(O(n\log^2n)\)。
260908 模拟赛 D
CF2249E2 String (Hard Version)
CF2246F Whoname and Unsorted Array
对于大多数情况，扫描 \(n\to 3\)，对 \(pos[i]\) 操作即可。若 \(pos[i]=n\)，也可以在 \(3\) 次内构造。最后，如果末尾是 \(12\) 也是容易在 \(n+eps\) 次构造，否则先把 \(2\) 操作过去，若 \(n\) 是偶数则无解，否则也是可以构造的。
P11983 [JOIST 2025] 展览会 3 / Exhibition 3
CF2255E2 What Will Remain at the End? (Hard Version)
*CF2239C Revival
需要想到倒着填，这样可以知道前面有哪些数，对每一位二分答案，用树状数组算出逆序对，方案也是唯一的。