CF2201D 题解

前言

思路

题意：称一个区间对 $([l_1,r_1],[l_2,r_2])$ 是好的，当且仅当可重集 $S=\{a_{l_1},a_{l_1+1},\cdots ,a_{r_1}\},T=\{a_{l_2},a_{l_2+1},\cdots ,a_{r_2}\}$ 满足 $S=T$。单点修改，每次输出所有好的区间对的区间长度最大值 $k_{\max}$ 和区间长度为 $k_{\max}$ 的区间对的个数 $f$。

两个可重集相等，上来直接和哈希变成两个区间和相等，吗？那就倒闭了，不可做的。发现这个限制看起来非常强，尝试找一下性质将其弱化。首先观察到两个区间一定有交或至少是相邻才可能成为答案，否则不如把中间也选上。

手摸一下样例或者自己造几组数据，发现大部分情况的答案都满足 $a_{l_1}=a_{r_2}$，即两侧不交的区间长度为 $1$。这给了我们一个很紧的区间长下界：$\max\limits_{a_i=a_j,i>j}\{i-j\}$。考虑什么时候两侧不交的区间长度 $>1$，实际的最大区间长度还能大于等于这个：

手玩得出此时两侧不交区间元素按位置一一对应时，总长度才可能与两侧长度 $=1$ 时相等，其余情况是严格劣于 $=1$ 的。于是我们证明了第一问的答案就是上面说的下界，可以用 set 维护。

考虑第二问如何计数：前面我们发现两侧不交区间长度 $=x$ 时，其实质上是被 $x$ 个相邻的 $1$ 拼起来的。考虑对每种长度维护该长度下所有区间左端点的连续段，每个长度为 $l$ 的连续段有 $\binom{l}{2}$ 个区间对。同样用 set 维护段，每次修改的时候分裂或合并并计算贡献即可。总复杂度 $\mathcal{O}(n\log n)$。

其实这个题的难点并不在于最后的数据结构维护，而在于前面的观察和转化，一步步将很强的限制拆解成可维护的东西。