P9058 [Ynoi2004] rpmtdq
区间两两贡献最值，考虑找支配点对。
一对点 \((u,v)\) 是支配点当他们之间不存在 \(p \in [u,v]\)，这自然引出了点分治的结构。
设分治中心为 \(r\)，求出当前子树内所有 \(x\) 与 \(r\) 的距离 \(dis\)，上面的判定等价于 \(\max(dis_u, dis_v) < \max_{i = l+1}^{r-1} dis_i\)。
这里的偏序关系可以直接用 \(\text{std::set}\) 维护前驱后继，但更好的做法是维护 \(dis\) 的一个单调栈，设加入 \(x\) 后第一个弹栈的点为 \(y\)，则 \((x,y)\) 是一个支配点对，根据点分治的复杂度分析，支配点对数量是 \(O(n \log n)\) 的。
求出所有支配点对后扫描线 + 树状数组处理询问，时间复杂度 \(O(n \log ^2n + q \log n)\)。
总结：
- 区间两两贡献最值，考虑找支配点对
- 需要熟悉结构和解法的对应
P8340 [AHOI2022] 山河重整
合法子集的充要条件是所有小于 \(i\) 的数之和大于等于 \(i\)，这里不加证明。
考虑一个简单的 dp，\(f_{i,j}\) 表示前 \(i\) 个数的子集能构成 \([1,j]\) 的方案。
这个 dp 很难继续优化，因为第二维的信息被压缩，转移没办法化简。
考虑补集转化，枚举断点容斥，设 \(f_i\) 表示前 \(i\) 个数能表出 \([1,i]\)，但不能表出 \(i+1\) 的方案数，答案为 \(2^n - \sum f_i \times 2^{n - i - 1}\)。
那么这个 \(f\) 显然要容斥，设 \(g_i\) 表示 \(i\) 的互异拆分数，则 \(f_i = g_i - \sum f_j \times v(j, i) = g_i - h_i\)，其中 \(j + 1\) 不能选，于是 \(v(j,i)\) 就是 \([j+2,i]\) 中选若干个不同数和为 \(i - j\) 的方案数。
\(g\) 的求解是经典的，把拆分的行列互换做完全背包状物即可，类似可以求 \(h\)，贡献形式为 \(f_j \to h_{j + (j + 2) \times i}\)。
现在唯一的问题是转移 \(h\) 需要先求解 \(f\)，我们有 \(j + (j + 2) \times i > 2 \times j\)，于是可以用倍增的方式先求前一半的 \(f,h\) 再转移给后一半，时间复杂度 \(n \sqrt n + \frac{n \sqrt n}{2} + \frac{n \sqrt n}{4} + ... = O(n \sqrt n)\)。
总结：
- 原问题的判定显然要绕过背包，于是考虑贪心
- 常见的补集转化
- 维度切换（适用条件：）
- 不知道怎么容斥可以套常见模型：恰好 - 至少
P5549 [BJ United Round #3] 观察星象
考虑二分答案，枚举圆上的一个点，其它每个点我们可以计算出它对于当前圆在哪个夹角区间内，进行一遍前缀和即可查找出是否存在一个夹角使得该圆包含 \(m\) 个点。
考虑优化，实际上我们每次求出了一个点对应的最小半径，而后面对其他点的二分中没用用到这个信息，基于这点，记录当前答案 \(ans\)，随机打乱序列并扫描，每次可以用一次 check 求出当前点答案是否 $ < ans$，否则跳过这个点，这样期望的 check 次数是 \(O(n + \log n\log \frac{x}{eps})\)，其中一个 \(\log\) 是单调栈期望长度，总时间复杂度 \(O((n + \log n\log \frac{x}{eps}) n\log n)\)。
总结：
- 考虑小结构到大结构的投影
- 充分利用已有信息，适用：
P8543 「Wdoi-2」纯粹的复仇女神
如果对这个嵌套结构比较熟悉，可以直接考虑扫描线 + 单调栈。
基于这个转化后观察得到，每个点的贡献是一个矩形，问题等价于矩形 \(\max\) 单点查询，使用标记永久化的树套树可以轻松完成，时间复杂度 \(O(n \log^2 n)\)。
总结：
- 二维信息可以直接放在平面上。
- 最值结构基于笛卡尔树考虑。
CF1517F Reunion
设有空的点为白点，没有空的点为黑点。
枚举半径 \(r\)，转成求点集半径 \(\geq r\) 的方案。
一个方案的半径大于等于 \(r\) 当且仅当存在一个点使得距离它最近的黑点与它的距离大于 \(r\)。
设 \(f_{i,j}\)表示以 \(i\) 为根的子树内部距离 \(i\) 最近的黑点的距离为 \(j\) 的方案数。
考虑为什么这个状态无法完整计数？因为没有满足子树外的限制，即有其他点可能成为聚会中心，于是在这基础上记录满足子树内距离其最近的黑点与其距离大于 \(r\) 的限制，可能成为聚会中心的点（称之为预备点）的深度。
这个状态是 \(O(n^2)\) 的，而两个维度记录的都是深度，引导我们考虑一些偏序关系，若子树内已经存在预备点，那么它们的覆盖关系是包含的，没有必要再考虑距离 \(i\) 最近的黑点与 \(i\) 的距离。
转移时合并两颗子树，算上枚举 \(r\)，总时间复杂度 \(O(n^3)\)。
总结：
- 相似的 dp 状态考虑分离，可以利用偏序等关系。
- 我们已知树形 dp 不能记录子树外信息，所以要考虑内外的转换。
[AGC020E] Encoding Subsets
单个 \(0/1\) 串的判定可以使用区间 dp。
考虑将 \(0/1\) 串压缩进一个整形，枚举划分转移，注意到这个限制非常严格，所以不妨猜想状态数很小，记忆化搜索可以通过。
总结：
- 考虑限制的松紧来排除做法/寻找方向。
P8329 [ZJOI2022] 树
可以肯定这个问题需要 dp，转移的时候要决策每个点在两颗树上的父亲，于是需要记录非叶子节点数量，等价于钦定了叶子节点（数量）。
设 \(f(S), g(T)\) 分别表示第一棵树的叶子集合恰好为 \(S\)，第二棵树的叶子集合恰好为 \(T\) 的方案数，则：
\(ans = \sum_{S, T} [S \cup T = \{1, 2, \dots, n\}][S \cap T = \varnothing] f(S)g(T)\)
考虑消除并集的限制，这必然需要容斥，套用恰好 - 至少的模型，设 \(f'(S'), g'(T')\) 分别表示钦定 \(S'\) 为第一棵树的叶子，\(T\) 为第二棵树的叶子的方案数。由子集反演容易得到：
于是：
此时 dp 只需要记录 \(S',T'\) 的大小，容斥系数只和当前点与 \(S',T'\) 的关系有关，时间复杂度 \(O(n^3)\)。
总结：
- 尝试从解法的结构反推具体内容