1011联考题解

首先特判掉 $a$ 中所有元素相同的情况。

容易发现答案有一个下界：$a$ 中众数出现的次数加一。

具体的，记众数为 $\text{A}$，任意一个其他的数为 $\text{B}$。那么 $b,c$ 形如 $\text{..A..A..B..A..A..A..}$。显然可以通过循环移位使得 $b,c$ 中只包含 $\text{A}$ 和 $\text{B}$ 的子序列相等。

尝试构造取到这个下界。 一种构造方案是 $b$ 为 $a$ 升序排列后的结果，$c$ 通过不断降序取 $a$ 中剩余元素各一个得到。

例如：$a=\{1,3,2,4,2,3,4,4\}$，则构造 $b=\{1,2,2,3,3,4,4,4\},c=\{4,3,2,1,4,3,2,4,3,4\}$。容易发现上述构造符合要求。

问题本质即为区间笛卡尔树所有子树 $size$ 和。

考虑算 $a_i$ 结点在整个序列的笛卡尔树 $size$ 大小，考虑找到 $i$ 左边第一个比他大的位置 $+1$,右边第一个比他大的位置 $-1$，分别记为 $l_i,r_i$，它的 $size$ 即为 $r_i-l_i+1$，加上每次询问区间的限制 $[ql,qr]$ 即为 $\sum\limits_{i=ql}^{qr}(\min(qr,r_i)-max(ql,l_i)+1)$。

分别做 $\min(qr,r_i),\max(ql,l_i)$，这里以 $\min(qr,r_i)$ 为例：

离线做扫描线，对于 $i$ 维护每个 $j$（$j\le i$）此时的 $\min(i,l_j)$，按 $l_j$ 排序，在 $i>l_j$ 时单点修改即可。

$\max(ql,l_i)$ 是类似的。

时间复杂度 $O(n\log n)$。

考虑 $G'$ 合法的条件。有一个显然的充要条件是对于每个环，$G'$ 中权值最大的边与 $G$ 中权值最大的边相同。

尝试刻画边之间的大小限制。按边权从小到大加边，设当前加入的边为 $e$，那么限制 $e$ 的边权大于加边后 $e$ 所在点双中的其他所有边。实际上，对于每个点双，取这个点双最新出现的边作为代表边，那么如果在 $e$ 加入前 $u,v$ 位于同一点双中，只需要限制 $e$ 的边权大于这个点双的代表边。

否则限制 $e$ 大于 $u$ 所在边双代表边和 $v$ 所在点双代表边。 发现上述限制关系构成一棵森林。我们需要求该森林的拓扑序个数。根据经典结论，设 $e$ 加边后 $e$ 所在点双大小为 $sz_e$，答案即为 $\frac{m!}{\prod sz_e}$。暴力实现上述做法复杂度 $O(n^2)$。

现在我们只需要动态加边维护点双。为了方便实现，可以先加入 $G$ 的最小生成树上的所有边。动态维护圆方树，对于每个圆点 $u$，用并查集维护 $u$ 的父亲（一个方点）。当前的设当前加入的边为 $(u,v)$，如果 $\text{LCA}(u,v)$ 是一个方点，则把路径上所有方点合并到 $\text{LCA}(u,v)$，否则合并到 $fa_{\text{LCA}(u,v)}$。找到路径上的方点只需要不断跳 $u,v$ 中 $dep$ 较大的一个即可。复杂度 $O(n\log n)$。

记 $S[l,r]$ 表示可重集 $\{a_l,a_{l+1},\ldots,a_r\}$。对于每个 $i$，记 $nxt_i$ 表示满足 $j>i,a_j=a_i$ 的 $j$，如果不存在则为 $-1$。

对于一个区间 $[l,r]$，如果存在区间 $[l',r']$ 满足 $S[l,r]=S[l',r']$ 且 $r<l'$，则这等价于 $r-l+1=r'-l'+1$ 且 $\min\limits_{i\in[l,r]}nxt_i=l',\max\limits_{i\in[l,r]}nxt_i=r'$。这还意味着 $[l',r']$ 是唯一的满足 $S[l,r]=S[l',r']$ 的区间 $[l',r']$。我们称 $[l',r']$ 是 $[l,r]$ 的关键区间。

考虑一个大于两个集合构成的等价类 $\{[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\}$。我们钦定 $l_i<l_{i+1}$。容易发现这种情况只会发生在 $r_1\ge l_k$ 时。发现对于相交的 $[l,r]$ 与 $[l',r']$（$l\le l'$），$S[l,r]=S[l',r']$ 当且仅当 $[r+1,r']$ 是 $[l,l'-1]$ 的关键区间。

我们希望对于 $[l_i,r_i]$ 只减去 $[l_{i+1},r_{i+1}]$ 的贡献方便统计。考虑如下算法：先默认答案为 $\frac{n\times(n+1)}{2}$，枚举 $l$，增加 $r$，如果存在 $[l',r']$ 且 $l'\neq r+1$，则将答案减一；如果 $l'$ 对于这个 $l$ 首次出现，则将答案额外减一。容易发现上述算法的正确性。直接实现复杂度小常数 $O(n^2)$。

尝试加速统计。从右到左扫描 $l$，对于每个 $r$，维护 $mn_r,val_r$ 表示 $\min\limits_{i\in[l,r]}nxt_i$ 和 $\max\limits_{i\in[l,r]}nxt_i-\min\limits_{i\in[l,r]}nxt_i-(r-l)$。这可以通过一个经典的单调栈技巧实现（通过单调栈将 $\text{cmax,cmin}$ 操作转为区间加减）。需要统计所有 $sum_r=0$ 的位置以及满足 $sum_r=0$ 的位置中 $mn_r$ 出现的种数。由于 $sum_r\ge0$，所以统计 $sum_r=0$ 的个数只需要记录 $sum_r$ 的最小值以及最小值的个数。由于 $mn_r$ 不增，种数即为颜色段数。这些信息都是容易合并的，直接用线段树维护即可，复杂度 $O(n\log n)$。