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

解题报告

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最优解（时间，空间，代码长度），想要的可以私信我。