回文路径
题意：\(2 \times n\) 的网格，每个格子有一个字符。从任意位置开始，每次向右/下走一格，任意位置停止。求路径是回文串的最大长度。
数据范围：\(n \le 10^5\)。
枚举回文中心 \(p\)。设 \(p\) 在第二行，假设他能在本行拓展到 \(s_2[l, r]\)，然后从 \(l\) 往上走，使得 \(s_1[l^{\prime}, l]\) 和 \(s_2[r + 1, r^{\prime}]\) 匹配。
如果路径转折点 \(x \in (l, p)\)，一定要满足 \(s_1[l - 1 ,x] = s_2[l, x]\)，才有可能与原路径长度相等。不可能超过原路径。submission
正方形计数
题意：给定格点凸 \(n\) 边形的顶点 \((x_i, y_i)\)。假定 \(S\) 代表该 \(n\) 边形内部与边上的格点集合。
求从 \(S\) 中选择四个互不相同无顺序点 \((x,y,z,w)\) 的方案数，使得 \(x,y,z,w\) 构成正方形。\(n \le 8,\ 0\le x_i, y_i \le 2000\)。
独立
题意：给定一棵 \(n\) 个点的树和正整数 \(m\)，每个点的权值在 \([1,m]\) 中等概率独立随机。
求不同方案的最大权独立集大小之和。\(1 \le n \le 2000, 1\le m \le 10^8\)。
分流器
题意：
排队
题意：给定 \(n\) 个区间 \([l_i, r_i]\)，定义 \(f_i(x) = x + [l_i \le x \le r_i]\)。
\(q\) 组询问，每次给出 \([L, R]\)，输出 \(f_R(f_{R - 1}(\cdots f_L(0)))\)。\(1 \le n, q \le 10^6, 0 \le l_i \le r_i \le n\)。
重要观察：对于 \(i < j\)， 有 \(f(i, r) \ge f(j, r)\)。
假设 \([i, j)\) 已经累计到 \(x\)，\(f(j, r)\) 从 \(0\) 开始累计，始终满足 \(f(j, r) \le f(i, r)\)，如果两者相等，则达到相同局面，后续增量也相同。
从左往右做扫描线，用数据结构维护所有的 \(f(i, r)\)，根据上述结论，随着 \(i\) 的增大，答案不增。
也就是说，答案在 \([l_r, r_r]\) 之间的 \(i\) 是一段连续区间，线段树上二分然后区间加。submission
最短路径
水镜
题意：给定长度为 \(n\) 的正整数序列 \(\{h\}\)，求满足以下条件的二元组 \((u, v)\) 对数。
- \(1 \le u < v \le n\)。
- 存在正实数 \(L\) 和一个长度为 \(v - u + 1\) 的序列 \(\{r\}\) 满足 \(r_i \in \{h_i, 2L - h_i\}\)。
- \(\forall i \in [u, v),\ r_i < r_{i + 1}\)。
设 \(p_i = \max(h_i, 2L - h_i)\)。由于 \(h_i, 2L - h_i\) 关于 \(L\) 对称，把序列 \(r\) 分割成 \(< L\) 和 \(\ge L\) 两部分。
小于的部分 \(\min(h_i, 2L - h_i)\) 单调递增，也就是 \(p_i\) 单调递减；另一部分 \(p_i\) 单调递增。
序列合法当且仅当存在 \(t \in [l, r)\) 使得 \(p_l > p_{l + 1} > \cdots > p_t ? p_{t + 1} < \cdots < p_{r}\)。其中 \(?\) 表示大小关系任意。
注意到 \(p_t = p_{t + 1} = L\) 的特殊情况，此时只要使 \(L\) 向下移 \(\epsilon\) 即可使 \([l, r]\) 合法。
直接统计条件过多，正难则反。如果存在 \(i \in (l, r)\) 使得 \(p_{i - 1} \le p_i \ge p_{i + 1}\)，则序列非法，这是充要条件。
如果 \(h_i > h_{i + 1}\)：
\[\begin{aligned} p_i \ge p_{i + 1} \implies L \le \dfrac{h_i + h_{i + 1}}{2}\\ p_i \le p_{i + 1} \implies L \ge \dfrac{h_i + h_{i + 1}}{2}\\ \end{aligned} \]\(h_i < h_{i + 1}\) 的情况同理。如果 \(h_i = h_{i + 1}\)，说明满足 \(p_{i} \ge p_{i + 1}\) 的 \(L\) 的范围是全集 \(U\)。
非法条件 \(p_{i - 1} \le p_i \ge p_{i + 1}\) 实际对应了 \(L\) 的一个取值范围，设为 \(I_i\)。
\([l, r]\) 非法当且仅当 \(\bigcup_{i = l + 1}^{r - 1} I_i = U\)，说明没有任何一个 \(L\) 的取值能使 \([l, r]\) 合法。
扫描线统计有多少个数对 \(l\le r\) 使得 \(\bigcup_{i = l}^{r} I_i = U\)，这和非法区间一一对应。
假设当前在 \(r\)，我们要找到最大的 \(l\) 使得范围之并是全集，那么对于所有 \(l^{\prime} \le l\) 的并也是全集。
把 \(I_r\) 范围内的数全部覆盖成 \(r\)，那么要找的 \(l\) 即全局最小值（没被覆盖的位置为 \(0\)）。
\(n - 1\) 个关键点 \(\dfrac{h_i + h_{i + 1}}{2}\) 把值域分成 \(n\) 块，每块中间再选一个与边界不同的代表点，这样就能表示 \(I_i\) 及其并（与全集 \(U\) 的关系）。
时间复杂度 \(O(n\log n)\)。submission