自动搬运

查看原文

来自洛谷，原作者为

	Zzzcr **

搬运于2025-08-24 23:12:39，当前版本为作者最后更新于2025-04-21 10:42:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

代码在写了 qwq。

问题不弱于区间逆序对，据说复杂度是单根号的，所以块长不设元了直接当做 $\mathcal{O}(n^{\frac1 2})$，下文中称第 $i$ 个序列块为 $B_i$，假设 $n,q$ 同阶。

区间数对子，考虑对每个数每种所在情况分别处理。

散，整块内部：

从前往后插入元素，在线求全局答案是容易做到单 log 的，求出每个块的前后缀的答案即可。

两整块之间：

令 $i<j$，记 $B_i$ 与 $B_j$ 之间的贡献为 $p_{i,j}$，钦定 $B_j$ 中只选了一个数，另一种情况是对称的。后文中这种对称的情形也只会讨论一侧。

考虑将 $1 \sim n$ 从小到大插入序列，并记录每个块中的顺序对数量，可以在插入的时候暴力维护。显然，插入的这个数所在的块会对前面的每个块造成该块内部顺序对数量的贡献，同样暴力维护。最后对 $p$ 做二维前缀和即可。

左散块，中间，右散块各选一个：

首先可以处理出来 $c_{i,j}$ 表示前 $i$ 块 $\le j$ 的数的数量，这个待会儿要用。

记录下来每个块内部排完序后的样子，和排完序后的每个元素在原序列中的下标，这样就能把两侧散块归并排序了。

记左散块为第 $\text{bl}$ 块，右散块为第 $\text{br}$ 块，考虑从小到大插入散块的元素并计入贡献，考虑左散块的元素 $x$ 和右散块的元素 $y$，对答案造成的贡献为 $c_{\text{br}-1,y-1}-c_{\text{bl},y-1}-c_{\text{br}-1,x}+c_{\text{bl},x}$，逐个插入可以直接做。

三整块之间：

枚举左侧和右侧的块 $B_i,B_j$，记 $h_{i,j}$ 为在 $B_i$ 和 $B_j$ 之间任选一个整块的答案的和，对每个 $i,j$ 按照“左散块，中间，右散块各选一个”的方法做一遍，然后做二维前缀和即可。

散块之间：

只考虑左侧选两个的情况。要做的是枚举右散块每个值 $z$，求左散块中有几个顺序对 $x<y$ 使得 $y<z$。

从小往大枚举右散块元素，对左散块做双指针，容易求出每个右散块元素的贡献。

同侧散块选两个，整块选一个：

只考虑左侧选两个的情况。从小到大枚举左散块每个值作为中间的数，比它大的数个数容易用 $c$ 表示。

散块选择一个，整块选择两个：

假设是在左散块中选择一个。

枚举散块元素 $v$ 后，求出整块构成的区间中满足限制的顺序对（即，二元组 $(a,b)$ 使得 $v<a<b$）是困难的，不妨求出整块的前缀的答案，再容斥减掉多余部分。

预处理 $t_{i,j}$ 表示在前 $i$ 块选择两个元素构成顺序对 $(a,b)$ 使得 $j<a<b$ 的方案。可以仿照之前的过程，从大到小插入元素。

假设枚举到了散块中的元素 $v$，记左散块为第 $\text{bl}$ 块，右散块为第 $\text{br}$ 块，贡献显然为

$ \ t_{\text{br}-1,v}-t_{\text{bl},v}-\sum_{i=1}^{\text{bl}}\sum_{x\in B_i}\sum_{j=\text{bl}+1}^{\text{br}-1}\sum_{y\in B_j}[x<y<v] $

最后那个和式的意义是跨过块分界线的点对数量，这是可以预处理的，考虑先枚举 $\text{bl}$。

将第 $1\sim \text{bl}$ 块排序，记前 $\text{bl}$ 块被排序后的序列为 $A$。维护数组 $r$，$r_i$ 表示顺序对 $(A_i,*)$ 的数量。再从小到大枚举 $\text{br}$，向后插入一个元素相当于对 $r$ 做前缀 $+1$，随后对第 $\text{bl}$ 块中的每个值 $v$ 求前缀和 $\sum_{i=1}^vr_i$。注意到查询的位置只有 $\mathcal{O}(n^{\frac1 2})$ 个，考虑只维护这些值。那么前缀 $+1$ 就能被拆成两个能用差分完成的修改，枚举到下一个 $\text{br}$ 时按照差分数组重构一次即可。

$l,r$ 同块情况：

维护每个元素向左 / 右 $1\sim n^{\frac1 2}$ 个元素中，有几个小于 / 大于它，累加起来就行。

上述过程精细实现后可以做到时空 $\mathcal{O}(n^{\frac3 2})$。