题意（简化版）
给出一个长度为 \(2n\) 的序列 \(a_i\)，求将序列分割为若干个长度为偶数的区间，满足每个区间内都不含绝对众数（出现次数严格大于长度的一半的数）的方案数。
\(n\le 500000,\,a_i\le2n\)
解法
解法和官方题解大致相同，虽然官方题解我也没看太明白（
显然一定在偶数出断开，所以可以先将序列两两分组，即 \(p_i=(a_{2i-1}, a_{2i})\) ，变成由 \(n\) 个二元组组成的序列。
为方便叙述，这里将二元组 \(p_i\) 的第一个元素记作 \(x_i\)，第二个记作 \(y_i\)。
考虑 dp，用 \(f_i\) 表示前 \(i\) 个二元组的合法分割方案数，那么 \(f_i = \sum\limits_{(j, i]\,is\,available} f_j\)，发现统计合法的转移是一个比较困难的工作，考虑正难则反，使用总和减去不合法的转移，那么
那么如何统计不合法的转移呢，首先发现每个不合法的转移中只会有一个绝对众数，那么可以考虑枚举绝对众数，对于绝对众数 \(v\) 分别统计。
具体统计时，需要使用一个我不知道的绝对众数经典 trick，对于每个二元组 \(p_i\) 赋一个权值 \(w_i\)：若 \(x_i\) 和 \(y_i\) 都等于 \(v\)，\(w_i = 1\)；若 \(x_i\) 和 \(y_i\) 其中有一个为 \(v\)，\(w_i=0\)；若 \(x_i\) 和 \(y_i\) 都不为 \(v\)，\(w_i=-1\)。
那么 \(v\) 为某一区间的绝对众数当且仅当该段区间的权值和为正，所以可以对权值做前缀和。
于是当前 dp 到 \(i\)，枚举的绝对众数为 \(v\) 时，我们可以 对于每一权值前缀和 \(val\) 统计其对应的所有 \(j\) 的 \(f_j\) 之和 \(memo_{val}\)，即 \(memo_{val} = \sum\limits_{j=1}^n\left[\sum\limits_{k=1}^j w_k= val\right] f_j\)，由于 \(i\) 的权值前缀和 \(s\) 的变化是连续的，\(memo\) 的前缀和很容易维护。减去不合法方案只需让 \(f_i\) 减去 \(memo\) 的前 \(s-1\) 项的前缀和。
于是我们便得到了一个 \(\mathcal{O(n^2)}\) 的算法。
如何优化呢，发现我们 dp 时做了许多无用的操作，其实可以先对于每个绝对众数 \(v\) 求出所有有可能以 \(v\) 为绝对众数的区间的并集，这个并集大小是与 \(v\) 的出现次数同阶的，于是对于所有 \(v\)，这个并集大小的和是 \(\mathcal O(n)\) 的！
对于每个 \(v\)，它的并集一定是由多个彼此不相连的区间构成的，对于每个区间分别统计其 \(memo\) 并转移即可。
时间复杂度 \(\mathcal{O(n)}\)。