自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:26:52，当前版本为作者最后更新于2021-01-04 17:13:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$5\times 10^5$ 已成为常见的根号复杂度范围.jpg

本题可以分为两个部分，下面分别对其分析。

• 第一部分（预处理）

  我们对每个不同的数值进行考虑。考虑当前的数为 $v$，它的出现次数为 $c$。

  由于 $v$ 能产生贡献的区间的中点位置必须是 $v$，因此我们考虑枚举两个端点到中点的距离 $L$。$v$ 在区间的出现次数显然随着 $L$ 的增大而单调不降，且出现次数为 $0\sim c$。

  我们再对 $v$ 的每个不同的出现次数进行考虑。对于 $v$ 出现了 $i$ 次，它对应的 $L$ 是连续的，设为区间 $[l,r]$。我们可以找到一个 $m\in[l-1,r]$ 满足当 $L\in[l,m]$ 时，$v$ 是区间的众数，而当 $L\in[m+1,r]$ 时，$v$ 不是区间的众数。证明很简单，这里略去。

  因此我们可以使用二分来找到这个 $m$ 的值，从而能得出所有能产生贡献的 $L$ 的范围。由于总共有 $c$ 个不同的出现次数（$0$ 次不可能成为众数，故略去），因此可以得到 $c$ 个互不相交的范围。

  由于二分的时候还需要求区间众数，因此对于一个 $v$，求它的 $L$ 的范围需要 $O(c\sqrt n\log n)$ 或 $O(c\sqrt{n\log n})$ 的时间复杂度。而所有的 $v$ 的 $c_v$ 的和为 $n$，因此这部分的总时间复杂度为 $O(n\sqrt n\log n)$ 或 $O(n\sqrt{n\log n})$。这个复杂度还不能接受。

  ---

  考虑优化上述过程。

  容易发现，$c_v\gt \sqrt n$ 的不同的 $v$ 最多有 $\sqrt n$ 个，这部分我们可以暴力枚举 $L$ 并进行判断，时间复杂度 $O(n\sqrt n)$（记得把连续的 $L$ 并成一个区间，否则空间复杂度将为 $O(n\sqrt n)$）。

  而对于 $c_v\leq \sqrt n$ 的所有 $v$，我们不妨考虑枚举众数的出现次数。

  假设当前众数的出现次数为 $(k-1)$，我们可以在 $O(n)$ 内求出 $p_{1..n}$，其中 $p_i$ 表示最小的满足 $[i,j]$ 的区间众数出现次数为 $k$ 的 $j$。

  以下是求数组 $p$ 的方法：

  可以证明 $a_{p_i}$ 是区间 $[i,p_i]$ 的唯一众数，否则 $[i,p_i-1]$ 的众数的出现次数也为 $k$。

  同理，若 $a_i\neq a_{p_i}$，则 $[i+1,p_i]$ 的众数的出现次数也为 $k$。

  我们对一个 $[i,p_i]$ 的左端点不断按此法向右移动，得到的 $[j,p_i]$ 会满足 $a_j=a_{p_i}$，即 $p_i$ 是位置 $j$ 之后第 $(k-1)$ 个 $a_j$。

  考虑令 $q_i$ 表示 $i$ 之后第 $(k-1)$ 个 $a_i$ 的出现位置，那么对于一个 $i$，就有 $p_i=\min_{j>i} q_j$。

  也就是说 $p_i$ 是 $q_i$ 的后缀 $\min$ 数组。

  用 vector 按顺序存每个数值的出现位置，然后再对每个位置记一下它在 vector 里的下标，就可以 $O(1)$ 得到单个 $q_i$。

  那么这部分的时间复杂度为 $O(n)$。

  枚举可能的数值 $v$，并取出 $l,r$ 满足当且仅当 $L\in[l,r]$ 时，$v$ 的出现次数恰好为 $k$。

  我们在上面提到了二分这个 $m$，在二分的时候，我们需要判断的其实是，是否存在一个区间 $[s,t]\in[v-m,v+m]$ 满足 $[s,t]$ 的区间众数大于等于 $k$。而我们只需要对所有的 $i\in[v-m,v+m]$ 检查：满足 $[i,j]$ 的众数出现次数恰好为 $k$ 的最小的 $j$ 是否大于 $v+m$，这个 $j$ 就是上面我们求出的 $p_i$。而由于 $p_i$ 具有单调性，因此我们只需要检查 $p_{v-m}$ 是否大于 $v+m$ 即可。因此单次检验是 $O(1)$ 的，一次二分的复杂度就是 $O(\log n)$。

  由于所有的 $v$ 的 $c_v$ 总和为 $n$，因此这里的二分的次数不会超过 $n$ 次，时间复杂度为 $O(n\log n)$。

  而我们需要对每个 $k\leq \sqrt n$ 计算对应的 $p$ 数组，因此这部分的时间复杂度是 $O(n\sqrt n)$。

• 第二部分（回答询问）。

  我们接下来需要解决的问题如下：

  给定不超过 $n$ 个三元组 $(v,x,y)$ 满足 $x\leq y$。对每个三元组，枚举 $i\in[x,y]$，并令 $A_{v-i,v+i}$ 增加 $1$。

  $m$ 次询问，每次给定 $l,r$，求 $\sum\limits_{i=l}^r\sum\limits_{j=l}^r A_{i,j}$ 的值。

  这个问题有多种做法，这里介绍一种较方便且容易理解的做法（感谢 memset0 提供了该做法的思路）。

  上面这个二维的问题是比较容易想到的转化后的题意，不过我们还是直接讨论一个三元组 $(v,x,y)$ 对 $l,r$ 的贡献。

  令 $a$ 为 $[v-y,v-x]\cap[l,r]$ 的长度，$b$ 为 $[v+x,v+y]\cap[l,r]$ 的长度，则贡献为 $\min(a,b)$。

  令 $mid=\lfloor\frac{l+r}2\rfloor$，可以发现，当 $mid\leq v$ 时，总有 $a\geq b$，当 $mid\gt v$ 时，总有 $a\lt b$。

  那么我们对 $mid\leq v$ 和 $mid\gt v$ 两种情况分开统计贡献即可。每种情况都是一个简单的二维数点问题，使用离线树状数组解决即可，时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n+m)$。

综上，算法的时间复杂度为 $O(n\sqrt n+m\log n)$，空间复杂度为 $O(n+m)$，可以通过本题。