P3897 [湖南集训] Crazy Rabbit
考虑一个点到圆的两个切点构成的圆弧，如果两个点连线与圆不交，那么两端圆弧是相交但不包含的，且把一段圆弧取反不影响答案。
断环成链，原问题等价于选最多的区间 \((l,r)\) 满足对于所有 \(i <j\)，\(l_j < r_i\) 枚举起始区间做 LCS 即可，时间复杂度 \(O(n^2 \log n)\)。
总结：
- 利用投影描述复杂信息
P5906 【模板】回滚莫队&不删除莫队
在普通莫队中增加是容易的，删除较为困难，考虑如何避免删除。
对于左端点所属块相同的询问，我们按右端点排序，先处理出右边的前缀信息，每次把 \(l\) 指针拉到左端点所属块的右端，暴力修改信息，这样每次询问只需要左移 \(l\)，可以分析出复杂度为 \(O(q \log n)\)。
总结：
- 花费一定的代价把问题转化为熟知的，可做的形式
P5986 [PA2019] Szprotki i szczupaki
首先每次必然会选择小于 \(x\) 最大的数，且每次操作后如果不能大于 \(k\) 或者大于 \(x\) 最小的数，就失败了。
使用线段树维护数集，每两次操作后的大小必然大于第一次选择的数的两倍，时间复杂度 \(O(n \log n \log V)\)。
总结：
- 注意题目中自然的 \(\log\)
P4769 [NOI2018] 冒泡排序
通过一些简单的情况可以发现，排列中不存在长度 \(\geq 3\) 的下降子序列，由 Dilworth 引理这等价于可以划分成两个上升子序列。
记 \(f_{i, j}\) 为前 \(i\) 个的最大值为 \(j\) 后面 \(n - i\) 个位置的方案数，则:
\[ f_{i, j} = \sum_{k = j}^n f_{i + 1, k}\]考虑其组合意义，即从点 \(A(i, j)\) 走到 \(B(n, n)\) 的不与直线 \(y = x - 1\) 相交的方案数。
不考虑后者，答案为 \(\dbinom{n-i-1}{2n - i - j - 1}\)，考虑第一个相交的位置，经过直线的方案数即为从点 \((j + 1, i - 1)\) 出发到点 \((n, n)\) 的方案数，于是 \(f_{i,j} = \dbinom{n - i - 1}{2n - i - j - 1} - \dbinom{n - j - 2}{2n - i - j - 1}\)。
现在有字典序的限制，钦定一段前缀相同，可以得到最终答案为从 \((i,\max\limits_{j\leq i}q_j+1)\) 游走到 \(n,n\)，而且不走到线以上的方案数，类似地可以求，时间复杂度 \(O(\sum n)\)。
总结：
- 对于一个严格的限制（即不满足是容易的），一般其补集会有一个简单的判断，可以通过一些局部 / 边界情况来得到
- 字典序比较钦定前缀
P5537 【XR-3】系统设计
考虑 \(rt \to x\) 路径唯一，记为 \(p_x\)，考虑将 1 操作转化为由根节点开始，并将 \(p_x\) 接入 \(a_{[l, r]}\) 前，二分结束位置，问题变为查询一序列是否属于 \(p\)、在 \(p\) 中位置。
考虑哈希。利用线段树可将 2 操作变为线段树上单点修改区间，时间复杂度 \(O(n + m + q \log^2 m)\)
总结：
- 利用 Hash 处理一一对应的序列匹配问题
CF1641D Two Arrays
注意到 \(m\) 的范围很小，这启发我们在复杂度上带上一些 \(2^m\) 状的东西。
先做双指针，现在要计算当前是否存在不交的数组对。
写出数组 \(X,Y\) 的幂集 \(P_x,P_y\)，考察以下式子
\[\sum_{x\in P_x}\sum_{y\in P_y}[x=y](-1)^{|x|-1} \]它在 \(P_x, P_y\) 有交集时为 \(0\)，否则为 \(1\)。
使用 Hash 维护幂集，在双指针的过程中记录桶判断，时间复杂度 \(O(nm 2^m)\)。
总结：
- 范围很小的集合相交问题，考察其幂集