260927 - 261015

260924 D

考虑二分图匹配，两侧各有 \(n\) 个点，左部点 \(i\) 和所有满足 \([i<j]=[a_i<a_j]\wedge j\ne i\) 的右部点 \(j\) 之间连边。对于一组子序列划分，可以构造出完美匹配，反之也可以。

于是就只需要删除最少的点使得无向图上存在集合 \(S\) 使得 \(|N(S)|<|S|\)。若 \(S\) 和 \(N(S)\) 有交，注意到我们可以把交从 \(S\) 中删去，答案不劣。于是只需要在原图上找到 \(\min_{S,S\cap N(S)=\varnothing}\{|N(S)|-|S|\}\) 即可。于是 \(S\) 形成一条下降子序列，只需要简单 \(n^2\) dp，用二维前缀和计算 \(|N(S)|\) 即可。

qoj6111 Two Paths

如果 \(x,y\) 在直径的同一子树上，必有一个点走进直径，只有 \(O(1)\) 种情况。否则，设两点在直径上的祖先分别为 \(u,v\)，先处理至少一个点不走上直径，以及至少一个点不往 \((u,v)\) 内部走的情况（断一条边划分成两棵子树，分别用两棵子树内的直径更新答案）。然后若两点都往 \((u,v)\) 内部走，考虑对直径维护一棵线段树，每个区间维护一个凸包，查询时二分即可。为了做到单 \(\log\)，可以预先把询问按斜率排序，这样线段树的每个节点只需要扫一遍就行了，也就是 \(O((n+q)\log n)\)。

260929 C

考虑算一个连通块的答案，如果不是二分图那么比较平凡，否则注意到固定限制后合法的范围是一个区间，考虑点边容斥，于是剩下的方案数也是形如 \((\frac{1}{2}(m+2)(m+1))^n\)，然后还有二分连通图的计数，这玩意和连通图一样 \(\ln\) 一下就行了，最后 \(\exp\) 起来。

260929 D

第一步显然扫描线，为了支持乘法的撤销，考虑把 \(mod\) 的质因子记下来，并考虑标记永久化，然后同时还要维护历史和，历史和的 \(tag\) 在下传时需要乘以乘法 \(tag\)。复杂度 \(O(n\omega(mod)\log n)\)。

这玩意比跑 \(\omega(mod)\) 次扫描线（最后 CRT）的常数小得多，所以前者能过后者不行。

P12480 [集训队互测 2024] Classical Counting Problem

P9150 邮箱题

261001 B

经过 \(O(m2^n)\) 的预处理之后，转化成 \(\max_{\{S_1,\cdots,S_k\},~S_i\cap S_j=\varnothing}\sum f_{S_i}\)。这实际上可以 \(O(3^n)\) 做：设 \(f_{k,S}\) 表示选 \(k\) 个集合的最大值。对于一种方案，每次选择最高的剩余位，拿走包含它的 \(S_i\)，那么转移到 \(f_{k,S}\) 的有用的 \(f_{k-1,S-T}\) 需要满足 \(T\) 包含于 \(S\) 去掉最高的 \(k-1\) 位后的结果，这样复杂度形如等比数列，是 \(O(3^n)\) 的。

261001 C

qoj8602

求出区间内的最高位 \(k\)，那么 \(x\) 最终需要 \(\ge 2^k\)，并且答案为 \(len+x+\sum[a_i>x]\)。只保留 \(>2^k\) 的 \(cnt\) 个 \(a_i\)，答案改写为 \(cnt-\max\{\sum[a_i\le x]-x\}\)，将其看成是 Hall 定理，就是 \(a_i\) 可以匹配 \(\le a_i\) 的正整数，最大匹配是多少。这个匹配显然按任意顺序贪心都是对的。

考虑分别处理每组 \(a_i\in[2^k,2^{k+1})\)，对 \(r\) 从左往右扫描线，维护从右往左贪心的结果。每次 \(r\) 最优先匹配 \(a_r\)，此时最多拆掉前面的一组匹配。考虑对匹配中的 \(a_j\) 维护 \(c_i=i-\sum[a_j\le i]\)，那么匹配 \(a_r\) 后找到最小的 \(c_i=-1\) 的位置，显然需要拆掉 \([1,i]\) 中的一个匹配，因此拆掉位置最靠前的即可，用线段树维护。

qoj7071 Maximize the Ratio

先二分，显然凸性可以通过按极角顺序依次转移来处理，但我们需要枚举最下方的点。然而注意到每个点作为起点的答案是独立的，因此 random shuffle 后二分可以做到 \(O(n^3+n\log n\log V)\)。

P7123 [NEERC 2016] Indiana Jones and the Uniform Cave

P6596 How Many of Them

261005 D

注意到只需要最大化单次操作同时转化 01 的次数即可，不难猜测答案就是最多不重叠的 01 以及 01并k 子段数量，正确性显然。又有显然的贪心策略，只需要快速贪心两个 \(k\) 中间的部分，用线段树维护即可，需要对 \(k\) 扫描线。

261005 C

状态需要记录进入子树时的前缀最大值，显然对于一棵子树我们只关心 \(sz\) 个位置的值，转移形如单点查询，全局乘，合并数组，简洁的做法是维护差分数组，然后线段树合并即可。

P15654 [省选联考 2026] 工业系统

261006 C

显然只需要对每个连通块判断，能否在没有共用端点的情况下取到最大覆盖面积，最优解显然形如一个区间和上一个区间相交，但和上上区间无交。因此不难设计出一个 dp：\(f_i\) 表示当前区间右端点为 \(i\)，上个区间的右端点最小是多少。转移形如从区间中找到最小的 \(f_j<l_i\)，但区间查询很难做到线性。

考虑按 dp 值从小往大做，那么 \(j\) 就是更新了 \((f_j,j)\) 区间内的所有 \(l_i\)，而我们的枚举顺序使得我们只需要找到区间中还没填的位置填上就可以了，转移只需要单点查询。用并查集是 \(O(n\alpha(n))\)，其实可以用栈，这样复杂度线性。

261006 D

考虑一条边的贡献，设其划分出的两个连通块内点权的最小值分别为 \(x,y\)。不妨设查询的 \(u\) 在 \(x\) 连通块，那么贡献为 \(\max(a_u,y)-w\)，又因为 \(x\le a_u\) 所以其等于 \(\max(a_u,\max(x,y))-w\)。于是简单用线段树维护即可。

AT_agc049_e [AGC049E] Increment Decrement

P16416 【MX-X28-T5】「FAOI-R12」单人旅行

设 \(f_i\) 表示前 \(i\) 个人覆盖了前 \(i\) 个景区的方案数。考虑加入一段连续 \(k\) 个 \(c=i+1\) 的人，然后加入一个 \(c\ne i+1\) 的人，即可转移到 \(f_{i+k+1}\)。考虑怎么处理 \(c\ne i+1\) 的那个人，考虑容斥，用不管的方案数减去钦定其 \(c=i+1\) 的方案数。需要把不管的总人数记下来，最后乘以其的阶乘。

AT_agc038_e [AGC038E] Gachapon

\(\min-\max\) 容斥

qoj10202 Exotic..Ancient City

mst，转化成求连通块数量，维护最后两层的连通性。

CF1842G Tenzing and Random Operations

按组合意义拆贡献

qoj5246 括号划分

P8329 [ZJOI2022] 树

设左边表示第一棵树的非叶子，右边表示第二棵树的非叶子。对左边的叶子进行容斥，只需要记录 \(j\) 表示左边容斥之后可以作为父亲的节点。对右边节点用点值平移的 trick，记录 \(k\) 表示需要 \(k\) 个不同的点作为父亲。转移是 \(O(1)\) 的。

P11847 [USACO25FEB] True or False Test P

显然 \(k\) 越大决策点越靠左，于是对决策单调性分治即可，用主席树查前 \(k\) 小。

P5611 [Ynoi2013] D2T2

261013 B

对所有 \(1\) 的位置按按下标 \(\bmod q\) 分组，组内做相邻两项不超过 \(p\) 的保序回归，需要注意到如果所有点都至少向右平移一位，那么解也至少向右平移一位，因此组之间的解不会重合。

261013 C

按 kruskal 从小到大加边，注意到一组边可以被拆成 \(\log\) 组 \([u,u+2^k)\leftrightarrow[v,v+2^k)\) 之间的连边，于是按 \(k\) 分层，层内的区间看成点，考虑一组边什么时候是没用的，是当本层 \(u,v\) 之间已经存在一条异或和为 \(x\) 的路径时，这个可以用并查集和线性基维护（维护每个连通块的所有环）。第 \(i\) 层只会合并 \(\frac{n}{2^i}\) 次，每次合并是线性基的 \(O(i^2)\)，因此总复杂度是 \(O(n\sum \frac{i^2}{2^i})=O(n)\)。只有有用的边才向下递归，复杂度应该是 \(O(n\log V)\)。