自动搬运

查看原文

来自洛谷，原作者为

	LostKeyToReach 争取今年不退役 || int_stl. || 有意互关私。

搬运于2025-08-24 23:08:56，当前版本为作者最后更新于2025-01-28 08:55:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

本题解提供离线+树状数组+双指针做法，代码请根据思路自行实现。

请务必读完解题思路。

题目回顾

给定 $n, c, d$ 和 $\{a\}$，你有 $q$ 次询问，每次给出 $l, r$，求：

$$\sum_{l \le x \le y \le r}[c \le \text{inv}(x, y) \le d]. $$

解题思路

考虑转换原式。

$$\sum_{l \le x \le y \le r}[c \le \text{inv}(x, y) \le d] = \sum_{l \le x \le y \le r} [\text{inv}(x, y) \le d] - \sum_{l \le x \le y \le r} [\text{inv}(x, y) \le c - 1]. $$

接下来求解 $\displaystyle \sum_{l \le x \le y \le r} [\text{inv}(x, y) \le d]$。

定义 $L_{d}(r) = \min \{l \mid \text{inv}(l, r) \le d\}$，$\text{cnt}_{d}(r) = r - L_{d}(r) + 1$，$\text{ps}_{d}(r)$ 为 $\text{cnt}_{d}(r)$ 的前缀和。

• $L_{d}(r)$：表示以 $r$ 为右端点时最小的 $l$ 使得 $[l, r]$ 区间的逆序对数量 $\le d$，这可以使用「双指针 + 树状数组」的方法来实现，具体思路如下：

  • 维护一个窗口 $[l, r]$ 及当前窗口的逆序对数量 $\text{CurrInv}$，再开一个树状数组用于维护逆序对数量。
  • 枚举 $r$，每次加入 $a_r$ 时将 $\text{CurrInv}$ 加上「当前窗口里大于 $a_r$ 的数的个数」。
  • 如果 $\text{CurrInv} > d$，就移动 $l$ 向左收缩，同时将 $\text{CurrInv}$ 减去「当前窗口里小于 $a_l$ 的数的个数」直到 $\text{CurrInv} \le d$。
  • 操作结束后，$l$ 便为 $L_{d}(r)$。

• $\text{cnt}_d(r)$：表示使得 $\text{inv}(l, r) \le d$ 的 $l$ 的数量，将 $L_d(r)$ 求解完毕后计算 $r - L_d(r) + 1$ 即可。

• $\text{ps}_d(r)$：为 $\text{cnt}_d(r)$ 的前缀和，表示右端点为 $1 \sim r$ 时，有多少个子区间满足 $\text{inv}(l, r) \le d$。

对于这部分，我们对 $d$ 和 $c - 1$ 分别进行一次这样的计算。

至此，此部分求解完毕，接下来，我们思考一个问题：如何从上述信息，得到「区间 $[l,r]$ 内，有多少子区间的逆序对 $\le d$」？

固定 $r$，若我们只关心「右端点 = $r$」的子区间，逆序对 $\le d$ 的那些，其左端点 $x$ 满足：

$$x \ge L_d(r).$$

故此时子区间数量为：

$$r - L_d(r) + 1 = \text{cnt}_d(r).$$

是现在我们只想要「左端点 $x \ge l$ 且右端点为 $r$」的子区间，这些子区间的数量应该是：

$$f_d(r, l) = \begin{cases} \text{cnt}_d(r), &\quad L_d(r) \ge l,\\ r - l + 1, &\quad L_d(r) < l. \\ \end{cases} $$

那么我们再对 $[l, r]$ 中的 $f_d(k, l)$ 求和，便可得区间 $[l, r]$ 内、右端点为 $r$ 的所有子区间中满足逆序对 $\le d$ 的数量。

$$\begin{aligned} \sum_{k = l} ^ r f_d(k, l) &= \sum_{k = l} ^ r \text{cnt}_d(k) - \sum_{k \in S}\left[\text{cnt}_d(k) - (k - l + 1)\right] \\ &=[\text{ps}_d(r) - \text{ps}_d(l - 1)] - \sum_{k \in S}[l - L_d(k)]. \end{aligned} $$

其中 $S = \{k \in [l, r] \mid L_d(k) < l\}$。

接下来引入两个变量 $y_{l, r}$ 和 $z_{l, r}$ 用于求解 $\displaystyle\sum_{k \in S}[l - L_d(k)]$。

$$y_{l, r} = \sum_{k \in [l, r], L_d(k) < l}1.$$ $$z_{l, r} = \sum_{k \in [l, r], L_d(k) < l} L_d(k). $$

此时 $\displaystyle\sum_{k \in S}[l - L_d(k)] = l \times y_{l, r} - z_{l, r}$。

那么 $y_l$ 和 $z_l$ 该如何求解？我们发现 $L_d(k) < l$ 这个条件的存在增加了题目难度，那我们不妨开一个桶 $b$，$b_x$ 记录所有 $L_d(k) = x$ 的位置 $k$，处理询问时将 $x < l$ 的 $b_x$ 中的位置加入便可以方便地处理掉这个限制。

接下来，我们开两个树状数组 $\text{fc}$ 和 $\text{fv}$ 分别维护 $y_{l, r}$ 和 $z_{l, r}$，加入 $b_x$ 的位置时分别单点加 $1$ 和 $L_d(k)$ 即可。

同理，我们对 $d$ 和 $c - 1$ 分别做一次。

最后，设我们处理出来的答案为 $\text{ans}_d(i)$ 和 $\text{ans}_{c - 1}(i)$，直接输出 $\text{ans}_d(i) - \text{ans}_{c - 1}(i)$ 即可。

时间复杂度分析

• 预处理：$O(n \log n)$。
• 离线计算答案：$O((n + q) \log n)$。
• 总时间复杂度：$O((n + q) \log n)$。

可以轻松处理 $n, q \le 5 \times 10^5$ 的数据。

代码实现

请自行实现。