@xiaoziyao
2021-06-30T16:41:37.000000Z
字数 1360
阅读 1115
解题报告
P6774 [NOI2020] 时代的眼泪/P6579 [Ynoi2019] Happy Sugar Life解题报告:
提供一种线性空间的简单做法,参考了chasedeath神仙的写法。
前置知识:基本分块思想与能力(例题P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I)
给定长度为的排列,次询问区间内保留值域的数之后的顺序对。
这个做法相对套路,没有什么新颖的地方,适合刚学分块的萌新。
首先该问题不弱于区间逆序对,因此直接考虑序列分块,设块长为。
对于一次询问,我们要计算的是整块内部,整块对整块,散块内部,散块对散块,整块对散块共五种贡献。
考虑如何处理一个点与一个区间(不交)产生的贡献,不难发现区间可以差分为两个前缀,离线之后我们用值域分块就可以统计贡献了,复杂度是加询问次数的。
那么散块对散块和整块对散块就可以直接做了,即枚举散块每一个点并产生一次询问。这样时空是的,但是不难发现直接把整个散块挂在前缀上就做到了线性空间。
然后是整块内部,块内离散化一下,设为值域到值域的块内答案,这样就可以递推了。
对于散块内部的贡献,我们考虑把每次询问的散块询问挂在对应块的前/后缀上,然后枚举块并离散化,从左到右/从右到左(要分别做)加入块的每一个数,处理表示块内第小的值到第小的值在第小的值之后的个数,再枚举每个询问,不难发现产生了的贡献可以暴力计算,复杂度。
最后整块对整块,考虑在值域上差分,答案是值域的答案减去值域的答案。然后按值域从小到大用另一个序列分块加入,同时处理一个表示第个块到第个块对第个块的顺序对贡献,这样就可以了。
很显然,上面那样做会计入小于的值与在内的值的贡献,于是我们枚举每个块,做个前缀和减去这样的值就可以了。
时间复杂度为,空间复杂度为,设为根号级别的值就做到了时间空间线性。
这里顺便提一个散块内部比较好写的解法(我写的是这种):
考虑分治:每次把区间划分成两份,左区间与右区间的贡献直接用上面的方法,但不难发现这样会产生次询问。
设一个阈值,如果区间长度小于阈值就暴力,否则继续分治,总共会产生次询问,暴力的总复杂度为的,微调一下就没有问题了,时空复杂度是与上面一样的。
虽然比较短只有3.1k,但是还是写了一上午+一下午。(为什么有人写了46k哇,恐怖如斯)
目前是P6579 [Ynoi2019] Happy Sugar Life最优解(时间,空间,代码长度),想要的可以私信我。