自动搬运

查看原文

来自洛谷，原作者为

	LordLaffey 本森级驱逐舰——拉菲，舷号 DD-459

搬运于2025-08-24 22:53:40，当前版本为作者最后更新于2022-11-07 22:49:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

V 害人不浅啊。

这题是不弱于（或强于）区间逆序对的，所以直接尝试根号做法。而操作分块的做法是不行的，所以去考虑其他形式的分块。

首先注意到答案是可以差分的，并且互不影响。设 $f(l,x)$ 表示区间 $[l,x]$ 中的 $a_i$ 对于 $b_x$ 的贡献，那么就可以表示为 $f(1,x) - f(1,l-1)$。$f(1,x)$ 的贡献是平凡的，记录每个 $b_x$ 需要计算多少次 $f(1,x)$ 即可，可以随便维护。

之后考虑计算 $f(1,l-1)$ 的贡献，问题就转化成了：每次给出一个区间 $[l,r]$，对于每个 $j \in [l,r]$，使 $b_j$ 加上 $i \in [1,l-1]$ 中，$a_i \leq a_j$ 的 $i$ 的个数。这个问题的好处在于查询区间与操作区间不相交，所以每一个 $j$ 受到贡献的区间都是 $[1,l-1]$。考虑序列分块，设块长为 $B$。那么对于 $[1,l-1]$ 中的整块部分，每一个整块都对 $[l,r]$ 中的每一个 $b_j$ 造成了贡献，所以可以对于每一个块开一个树状数组，记录这个块对所有 $b$ 的贡献，区间加即可。

进了一步，现在还剩下 $[1,l-1]$ 的散块中对区间 $[l,r]$ 的贡献，不妨设散块为 $K$。由于散块中数字个数不超过 $B$，所以 $m$ 个操作的数字个数是 $O(mB)$ 级别的，考虑直接转化成二维数点的形式，但是直接插入的时间复杂度无法接受，考虑换一个角度思考。对于区间 $[l,r]$ 中的整块，受到 $a_i \in K$ 的影响是相同的，所以可以对于每一个序列块开一个支持可插入数点的数据结构，如果对于每一个块开一个值域分块的话，这样的时间复杂度是 $O(B^2) - O(B)$ 的，利用差分+树状数组，可以将时间复杂度平衡到 $O(B \log n) - O(B \log n)$。直接进行一个点的数即可。

最后是 $[1,l-1]$ 中的散块对 $[l,r]$ 散块的贡献，数字个数不会超过 $O(B)$ 个，可以直接归并统计。

单点查询就会特别简单，只需要将上述几种贡献合并即可。时间复杂度为 $O(m (\frac{n}{B} \log n + B \log n))$，取 $B = \sqrt{n}$ ，最优时间复杂度为 $O(m \sqrt{n} \log n)$。