题解：P11625 [迷宫寻路 Round 3] 迷宫寻路大赛
LostKeyToReach
·
·
题解
本题解提供离线+树状数组+双指针做法，代码请根据思路自行实现。
请务必读完解题思路。
题目回顾
给定 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, 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)$。
-
-
对于这部分，我们对 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 的数据。
代码实现
请自行实现。