自动搬运

查看原文

来自洛谷，原作者为

	whiteqwq 寻找着梦与现实的交点 在哪呢 在哪呢

搬运于2025-08-24 22:22:07，当前版本为作者最后更新于2021-06-30 16:41:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P6774 [NOI2020] 时代的眼泪/P6579 [Ynoi2019] Happy Sugar Life解题报告：

更好的阅读体验

提供一种线性空间的简单做法，参考了chasedeath神仙的写法。

前置知识：基本分块思想与能力（例题P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I）

题意

给定长度为 $n$ 的排列 $p$ ， $q$ 次询问区间 $[l,r]$ 内保留值域 $[a,b]$ 的数之后的顺序对。

$1\leqslant n\leqslant 10^5,1\leqslant q\leqslant 2\times 10^5$

分析

这个做法相对套路，没有什么新颖的地方，适合刚学分块的萌新。

首先该问题不弱于区间逆序对，因此直接考虑序列分块，设块长为 $B$ 。

对于一次询问 $[l,r,a,b]$ ，我们要计算的是整块内部，整块对整块，散块内部，散块对散块，整块对散块共五种贡献。

考虑如何处理一个点与一个区间（不交）产生的贡献，不难发现区间可以差分为两个前缀，离线之后我们用值域分块就可以统计贡献了，复杂度是 $O(n\sqrt n)$ 加询问次数的。

那么散块对散块和整块对散块就可以直接做了，即枚举散块每一个点并产生一次询问。这样时空是 $O(qB)$ 的，但是不难发现直接把整个散块挂在前缀上就做到了线性空间。

然后是整块内部，块内离散化一下，设 $r_{i,j}$ 为值域 $i$ 到值域 $j$ 的块内答案，这样就可以 $O(\frac{qn}{B}+nB)$ 递推了。

对于散块内部的贡献，我们考虑把每次询问的散块询问挂在对应块的前/后缀上，然后枚举块并离散化，从左到右/从右到左（要分别做）加入块的每一个数，处理 $s_{i,j}$ 表示块内第 $i$ 小的值到第 $j-1$ 小的值在第 $j$ 小的值之后的个数，再枚举每个询问，不难发现产生了的贡献可以暴力计算，复杂度 $O((n+q)B)$ 。

最后整块对整块，考虑在值域上差分，答案是值域 $[1,b]$ 的答案减去值域 $[1,a-1]$ 的答案。然后按值域从小到大用另一个序列分块 $O(1)$ 加入，同时处理一个 $t_{i,j}$ 表示第 $i$ 个块到第 $j-1$ 个块对第 $j$ 个块的顺序对贡献，这样就可以 $O(\frac{qn}{B}+nB)$ 了。

很显然，上面那样做会计入小于 $a$ 的值与在 $[a,b]$ 内的值的贡献，于是我们枚举每个块，做个前缀和减去这样的值就可以了。

时间复杂度为 $O((n+q)(\sqrt n+B)+\frac{nq}{B})$ ，空间复杂度为 $O(n+\frac{Bq}{S})$ ， $B$ 设为根号级别的值就做到了时间 $O(n\sqrt n)$ 空间线性。

这里顺便提一个散块内部比较好写的解法（我写的是这种）：

考虑分治：每次把区间划分成两份，左区间与右区间的贡献直接用上面的方法，但不难发现这样会产生 $O(qB)$ 次询问。

设一个阈值 $S$ ，如果区间长度小于阈值就 $O(n^2)$ 暴力，否则继续分治，总共会产生 $O(\frac{qB}{S})$ 次询问，暴力的总复杂度为 $O(qBS)$ 的，微调一下就没有问题了，时空复杂度是与上面一样的。

代码

虽然比较短只有3.1k，但是还是写了一上午+一下午。（为什么有人写了46k哇，恐怖如斯）

目前是P6579 [Ynoi2019] Happy Sugar Life最优解（时间，空间，代码长度），想要的可以私信我。