260531 - 260614
P7220 [JOISC 2020] 掃除
正经做法是画一个过 \((\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil)\) 的矩形，把原问题划分成矩形内的问题和两个子问题，这样深度只有 \(O(\log n)\)，所以用 set 暴力维护下放即可，复杂度 \(O(n\log^2 n)\)。
CF1534H Lost Nodes
通过一次子树内的询问，我们可以判断路径的一端是否在该子树内。如果瞎问一个很不优，所以问子树最优策略的第一个问题，这样做显然是下界。这样转移和换根都是简单的。
AT_agc017_f [AGC017F] Zigzag
对路径依次 dp，可以轮廓线 dp，距离一维的状态可以压缩到 mask 里面，复杂度 \(O(n^22^n)\)。
AT_agc019_f [AGC019F] Yes or No
每次肯定都是选择概率较大的选项，所以可以肯定可以用 keep or gamble 的方法做，但是太复杂了。注意到若 \(x\ne y\) 那么选对将会使 \(\max(x,y)\) 减一，若 \(x=y\) 则无论是否选对都不会改变 \(\max(x,y)\)，然后拆贡献算一下即可。
P14653 [集训队互测 2025] 你的互相追逐的头
首先要注意到点集直径上的两点一定始终向直径中心移动，然后所有点在遇到下一个点之前都不会回头，所以是走一条路径。然后我们从直径的一个端点出发，依次处理所有点，用一个栈维护当前点路径上的所有拐点（两个点相遇可能回头），加入前一个点时判断是否会在栈顶拐点之前相遇，若否则弹栈，时间复杂度 \(O(n\log\log n)\)，瓶颈在 \(k\) 级祖先。
AT_agc053_e [AGC053E] More Peaks More Fun
其实我们可以贪心的让左边的那个前缀尽可能长，这样就可以构造一个不会数重的充要条件：\(b_{p_i}>a_{p_{i+1}},~b_{q_i}>a_{q_{i+1}},~b_{p_{k_1}}<a_{p_{k_2}}\)。如果我们只对 \(p\) 计数，那么可以按照 \(b\) 从大到小插入，插入位置和前面一定合法，后面的位置需要满足 \(a_j<b_i\)，所以我们可以预处理出 \(pre_i\) 表示 \(b_j>b_i\) 且 \(a_j<b_i\) 的 \(j\) 的数量，这样答案就是 \(\prod (pre_i+1)\)。
考虑带上 \(q\) 怎么做，我们可以先枚举两个序列的最后一个位置，记为 \(x,y\)。这样对于 \(b_i>b_x\)，可以随便插入，贡献 \(pre_i+2\)；对于 \(b_y<b_i<b_x\)，下面可以随便插入，上面要看 \(a\)，所以贡献 \(pre_i+1\)；对于 \(b_i<b_y\) 都要看 \(a\) 所以贡献是 \(pre_i\)。处理出 \(pre\) 之后贡献是可以 \(O(n)\) 算出来的。
260602 A
给定一个长为 \(n\) 的序列 \(a\)，值域为 \([0,m]\) 的整数。求满足条件的长为 \(n\) 的序列 \(b\) 的数量：
- \(b\) 的字典序小于 \(a\)；
- \(b\) 每个前缀的 \(\operatorname{mex}\) 都小于等于 \(a\) 序列对应前缀的 \(\operatorname{mex}\)；
\(n,m\le 200\)
先考虑第二个限制，很自然的想到对 \(\operatorname{mex}\) 序列进行 dp 然后对原序列计数。考虑 \(\operatorname{mex}\) 序列的结构，形如要么不动，要么上升若干位置，上升的位置需要由之前不动的位置提供。于是可以记录有多少个不确定的位置，在上升的时候钦定一些下标等于当前位置，这样实际上是 \(O(n^4)\) 的（状态 \(O(n^3)\)，转移 \(O(n)\)）。优化也很简单，把等价类的决策放到加入不动的下标时即可，第三维状态变为等价类数量。
考虑处理第一个限制，形如钦定一个前缀，然后一个位置小于一个上界。我们只需要在加入不动点的时候额外考虑放入已经确定的等价类的情况，在上升的时候跳过已经确定出现过的数即可。对于 \(b_i\) 上界的限制，如果它小于当前 \(\operatorname{mex}\) 是平凡的，等于当前 \(\operatorname{mex}\) 是确定的，大于 \(\operatorname{mex}\) 只需要在状态中记一个 \(0/1\) 表示 \(k\) 个等价类中是否包含一个有上界限制的等价类。
260602 B
有 \(n\) 个人围着圆桌坐在一圈。你需要通过向交互库询问来确定每个人的位置，翻转或者旋转后的答案都被认为正确。你可以向交互库给出一个排列，\(n\) 个人按照你给出的顺序依次入座，交互库返回“两个邻居都比自己晚到”的人的集合。你需要在 \(60\) 次询问内确定 \(n\le 10^5\) 的答案。交互库不是自适应的。
将相邻的人连边，实际上是要确定所有边，询问实际上是返回和前缀没有边的点的集合。此时，如果我们已知一个独立集 \(S\)，我们可以通过两次二分求得 \(S\leftrightarrow \overline S\) 的边。考虑求出独立集 \(S\)，首先问出所有谷，然后把谷删掉再问可以得到离谷距离为 \(1\) 的位置，以此类推，峰会得到两边距离的更大值。然后选出距离为偶数的点，再把能加的峰加进去即可。
由于得到的独立集是极大的，因此不在独立集的元素不会形成长度超过 \(2\) 的连续段。考虑把 \(\overline S\) 继续分成两个独立集，可以考虑取 \(\overline S\) 的谷或者峰，记为 \(S_1\) 和 \(S_2=\overline S-S_1\)。由于 \(S_1\) 的每个元素至多只和 \(S_2\) 中有一条边，所以只需要一次二分。这样总共三次，找独立集只需要不超过相邻峰谷的最大距离次，这玩意在随机情况下显然不会太大。次数 \(3\log n~+\) 很小。可以取 \(S_1,S_2\) 中较大的进行二分可以提高成功率。
P6545 [CEOI 2014] The Wall
考虑左端点到一个村庄（哪个角都行）的最短路，根据定义这条路径至少有一个点被包含在墙内。此时如果路径不完全被包含在墙内，那么把交叉处的一段调整为最短路上的边是不劣的，所以所有这样的最短路都被完全包含在墙内。这样，所有村庄以及左上角的起点都被连成了一个连通块，而包住一个连通块显然就容易许多。只需要把点拆成 \(4\) 个，边拆成 \(2\) 条，然后跑一个最短路即可。
P10218 [省选联考 2024] 魔法手杖
首先有一种显然的 \(O(nk^2)\) 做法：二分答案，然后枚举 \(x\)。考虑优化，由于本质上就是让我们求满足 \(x\ge mid-\min\{a_i\}\) 的最大的 \(\sum [a_i\oplus x< mid]\times b_i\)，而 \([a_i\oplus x<mid]\) 可以进一步转化成 \(a_i\) 与 \(x\oplus mid\) 最高不同的位有 \(mid_t=1\)。这样，我们可以枚举 \(x\oplus mid\)，然后逐位试填 \(mid\)，由于 \(mid\) 更小时两个限制都更松，所以试填是对的。
这个容易直接优化到 \(O(nk)\)，考虑枚举 \(x\oplus mid\) 的过程中同时试填 \(mid\)，只需要把没填的末尾都填 \(0\)，\(x\) 都填 \(1\) 即可快速判定。
P11832 [省选联考 2025] 图排列
考虑树怎么做，我们尝试把 \(1\) 放到开头，发现这样所有子树都不能交叉，儿子的子树也不能交叉，显然直接按最小值排序即可。考虑连通图怎么做，首先需要发现可以把 \(1\) 旋转到开头，具体的只需要把 \(1\) 前面的东西倒着放到末尾即可。随后取出一棵以 \(1\) 为根的 dfs 树，那么 \(1\) 的子树仍然不能交叉，儿子的子树也不能交叉。考察反祖边造成的影响，发现反祖到父亲及以上的子树必须放到最前或者最后，反祖到父亲以上的子树必须和当前节点 \(u\) 同时在最前或者最后，这显然是充要的。
所以 \(u\) 不能有两棵反祖到父亲以上的子树，只有一棵的话我们只关心它在前面还是后面，反祖到父亲的子树不需要记录到状态。稍微分析一下还可得，从 \(u\) 出发的反祖边不会和子树的反祖边交叉，所以不用管。由于是排列所以只需要记录子树最优解的第一个值即可。对着 dp 值构造方案是容易的。
如果有多个连通块，显然不能交叉，所以用一个堆和一个栈合并即可。
260604 A
给定一个图，边有 \(0/1/2\) 的边权。你需要支持加边和删边（可以离线），查询有多少个二元组 \((a,b)\) 满足可以找到一棵有 \(a\) 条 \(0\) 边，\(b\) 条 \(1\) 边的生成树。
\(n,m,q\le 2\times 10^5\)
不难想到求出每种边的最少和最多数量，那么只要三种边的数量都在界内并且和为 \(n-1\) 就是合法的。
考虑证明，先把必须边都扔了，这样三种边的下界就都是 \(0\) 了。然后考虑只有两种边如何进行连续的调整，考虑 kruskal 的过程，只需要把少的边往最前面放，每次 \(+0\) 或者 \(+1\)，所以没问题。考虑第三种边，一条一条加，比如往 \(0\) 边最少 \(1\) 边最多的图上加，我们说明此时可以删掉一条 \(0\) 边（若存在）。其实根据非必须边的定义，因为 \(1\) 边最多所以一定可以。
使用 \(7\) 个线段树分治维护连通块数量即可。
260604 C
给定一棵以 \(n\) 号节点为根的树，保证父亲编号大于儿子节点。有一个 \(1\sim n\) 的排列 \(a\)。有若干次查询，每次给定 \(t,h,k\)，问 \(i\in [1,k]\) 的 \(a_i\) 有多少个满足深度小于 \(t\) 或者 \(t\) 级祖先的编号 \(\ge h\)。
\(n,q\le 2\times 10^5\)
考虑树分块，对每个关键点考虑从块内跨过该关键点的贡献，按照 \(k\) 扫描线，把块内 \(\le k\) 的 \(a_i\) 记进深度数组里，查询只需要知道关键点还需要跳几步，然后在深度数组上查一下即可。然后考虑块内贡献，直接把每个点在块内的 \(\le B\) 个祖先搞出来，用 \(B\) 个 \(O(1)-O(\sqrt n)\) 的分块维护每级祖先即可。
CF1332G No Monotone Triples
显然根据 Dilworth 定理，答案长度不超过 \(4\)。答案为 \(3\) 形如 \(132/231\)，答案为 \(4\) 形如两边的数夹在中间的两数之间，限制其实是二维的所以很容易。
AT_agc022_f [AGC022F] Checkers
就是对系数排列进行计数，所以显然要把系数相同的一起转移。由于系数都是形如 \((-1)^\alpha2^\beta\)，考虑枚举 \(\beta\)，只需在 dp 中记录 \(2^\beta\) 和 \(-2^\beta\) 的个数，转移时需要考虑把一些 \(2^\beta,-2^\beta\) 拆成 \((2^{\beta-1},-2^\beta),(-2^{\beta-1},2^\beta)\)，其实只关注二者数量之差，所以先枚举差再枚举具体的值。此外 \(\beta\) 实际上无需记录，所以复杂度 \(O(n^4)\)。
AT_arc161_f [ARC161F] Everywhere is Sparser than Whole (Judge)
先尝试找到导出子图使得 \(E-VD>0\)，问题形如一个最大权闭合子图，容易用网络流求解，建出图后发现不存在 \(\max\{E-VD\}> 0\) 充要于最大流等于 \(VD\)。然后考虑怎么判断存在一个子图使得 \(E-VD=0\)，对图的结构分析可得：对于这样一个子图 \(V\)，一条横跨 \(V\) 和 \(\overline V\) 的边一定是指向 \(\overline V\) 的边满流，所以将边按照满流的方向进行定向，等价于找到一个没有入度的 SCC，随便做即可。
P4348 [CERC2015] Cow Confinement
从右向左扫描线即可，维护矩形的删除和加入，同时维护每个位置向上第一个栅栏。删除矩形时，需要注意去重，通过手模可以猜出算重的充要条件是可以被删除矩形的右下角走到，证明似乎是容易的。
P6973 [NEERC 2016] List of Primes
涉及质数的数量不太多，通过打表可得需要用到前 \(317\) 个质数，总和不超过最后一个质数 \(2099\)。对着 dp 的过程构造方案是容易的。
AT_arc220_e [ARC220E] popcount ≥ K
P16574 [USACO26OPEN] Perfect Binary Trees
260609 B
给定一棵树，点有颜色，每次查询一条路径上出现次数多于 \(x\) 颜色的出现次数的颜色数量。强制在线。
\(n\le 10^5\)
显然树上莫队可以轻松解决离线问题。考虑改成在线，考虑树分块，显然我们可以通过预处理 \(O(1)\) 查询出某种颜色在某两个关键点之间路径上的出现次数，所以加入散块是简单的。对于整块，只需要把所有本质不同的出现次数搞出来，只有 \(\sqrt{2n}\) 个，容易用数组实现。
260609 C
有一个 \(n\) 个点的有向完全图，点有黑白颜色，记为 \(a_i\in\{B,W\}\)。保证 \(a_1=B,~a_2=W\)。边有红蓝颜色，一条边 \(u\to v\) 在 \([u<v]=[a_u=a_v]\) 时为红色，否则为蓝色。
你有一个红蓝颜色，若你当前位于 \(1\) 号点则立即变成蓝色，若位于 \(2\) 号点则变成红色。你只能走与自身颜色相同的边。你需要对 \(1\to 2\) 的路径进行计数，点和边可以经过多次，但是需要满足：
- \(3\sim n\) 的每个点至多被经过一次；
- 不能走出 \(x\to y\to x\) 的结构，即不能立即回头；
\(n\le 50\)
由于 \(u\to v\) 和 \(v\to u\) 颜色相反，所以第二个限制只是要求不能走 \(1\to 2\to 1\) 或 \(2\to 1\to 2\)。然后观察到路径的结构形如 \(1\to\cdots\to 1\to\cdots\to 2\to\cdots\to 1\cdots 2\)，我们需要在相邻两个 \(1\) 或 \(2\) 之间插入一条由 \(\ge 3\) 的点构成的链。需要发现我们只关心链两端的颜色，以及链内部边的颜色。进一步可以发现，把链倒过来可以改变边的颜色，所以我们不妨钦定所有链内部都是蓝色边，在最后拼接的时候再决定颜色。
因此我们可以把首尾颜色分别为 BB,BW,WB,WW 的四种链的数量都记进状态，然后按照点编号从小到大的顺序加入，每次考虑跳过当前点、新增一条链或者合并一些链，转移是容易的。
最后分讨一下，BB 不能插入，WB 和 BW 可以分别插入 \(1\to 1\) 和 \(2\to 2\) 之间，WW 可以插入 \(1\to 2\) 或者 \(2\to 1\)。注意到只需要把所有链任意排列，如果 \(?\to 1\) 衔接 \(2\to ?\) 就插入一个 \(1\to 2\) 的边；如果颜色相同就不用额外加边。由于不会有连续两条链为空，所以实际上是不重不漏的。