题解 P6774【[NOI2020] 时代的眼泪】

whiteqwq · 2021-06-30 16:37:54 · 题解

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

更好的阅读体验

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

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

题意

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

分析

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

首先该问题不弱于区间逆序对，因此直接考虑序列分块，设块长为 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最优解（时间，空间，代码长度），想要的可以私信我。