题意
给定一个长度为 \(2 \times n\) 的数列 \(S\)。
称一个数列是好的，当且仅当数列中的数可以由每次删除相邻两个 不同 的数的操作删空。
求划分该数列为若干好的字串的方案数。
Sol
集中注意力。
首先显然长度为奇数的序列是没法做的。
若序列存在绝对众数，则该序列一定无法删除，否则该序列一定能被删空
证明：若序列不存在绝对众数，显然每次一定能找到两个相邻不相同的数进行操作，所以一定能操作完。
考虑一个简单的 \(\text{dp}\)。
设 \(pos_{l, r} \in [0, 1]\) 表示区间 \([l, r]\) 是否存在绝对众数。
\[f_i = \sum_{j = 0} ^ {i - 2} [i - j \mod 2][pos_{j + 1, i}]f_j \\ \]显然该 \(\text{dp}\) 的复杂度为 \(O(n ^ 2)\)。
考虑使用 \(\text{CDQ}\) 分治优化。
注意到对于大多数情况，左边所有的状态都能直接转移到右边。
考虑先将左边求和，先转移，然后再减去绝对众数产生的贡献。
若一个序列有绝对众数，则它任意分成两段，至少有一段存在绝对众数
我们可以考虑分别处理出 \(\text{mid}\) 左边与右边的绝对众数。
显然能够成为绝对众数的数的个数不会超过 \(\log n\)。
考虑 \(s_p\) 能成为绝对众数的约束，设 \(i, j\) 为当前选择区间的左右端点，显然 \(i \le mid\)，且 \(j > mid\)。设 \(C_i, C_j\) 分别表示 \(mid\) 左边与右边，和 \(s_p\) 相同的数的个数。
由绝对众数的定义得：
\[(i - j + 1) < (C_i + C_j) \times 2 \]考虑化简：
\[i - j + 1 < 2C_i + 2C_j \]将含 \(i\) 的扔到一边，含 \(j\) 的扔到另一边：
\[i - 2C_i + 1 < j + 2C_j \]注意到该式子左右只和 \(i, j\) 分别有关。
考虑对于所有的 \(i\) 预处理 \(i - 2C_i + 1\)，放进一个桶里，求后缀和。
然后对于所有的 \(j\) 直接计算答案的贡献就完事了！
复杂度：\(O(n \log ^ 2 n)\)。
标签：Division,Good,text,众数,绝对,mid,ARC159F,2C,序列 From： https://www.cnblogs.com/cxqghzj/p/18174087