三道经典分块题的更优复杂度解法&[Ynoi2019模拟赛]题解

大概是一年前搞的东西了，一直都懒得发博客

1.强制在线的区间逆序对

目前我能做到 $O( n\sqrt m )$ 空间， $O( n\sqrt m )$ 时间

大概有5,6种做法吧，这里讲一个常数最小的

预处理前缀块到前缀的答案，然后每次可以大力差分为一堆已经预处理的东西，以及两个块的零散互相的贡献

前者已经预处理了，直接查表就可以了，后者可以归并计算

2.允许离线的区间逆序对

目前我能做到 $O( n + m )$ 空间， $O( n\sqrt m )$ 时间

这个算法是基于“莫队算法”的，个人将其命名为“莫队二次离线”，如果大家觉得有问题请提出然后我改掉就是

原理大概是把莫队抽象为 $O( n\sqrt m )$ 次查询区间中小于x的数的个数

然后差分为 $O( n\sqrt m )$ 次查询前缀中小于x的数的个数

然后可以发现这里有很大的不平衡——查询次数 $O( n\sqrt m )$ ，但是区间长度只有 $n$ ，也就是说不同的前缀只有 $n$ 个

考虑用一个 $O( \sqrt n )$ 插入， $O( 1 )$ 查询的rank的数据结构，即一个普通的值域分块来维护

这样就达到了我们需要的时间复杂度

如果存下每次询问，那由于莫队会造成 $O( n\sqrt m )$ 次前缀查询，所以空间复杂度还是很高的

考虑到莫队每次是一个区间到一个区间的转移，也就是说大部分查询是有规律的，这里是可以优化到 $O( n + m )$ 的空间的

目前这一步最优的实现方法是再大力差分一下，通过前缀对前缀的贡献，后缀到后缀的贡献，以及一个序列区间对一个前缀的贡献，后缀的贡献来表示每次莫队转移的时候造成的贡献，这个实现有着不错的常数以及代码复杂度

3.强制在线的区间众数查询

目前我能做到 $O( n )$ 空间， $O( n\sqrt m )$ 时间

这个算法并不是我独立提出的

考虑预处理块端点到块端点的众数，然后每次就需要查询 $O( n/\sqrt m )$ 个数加入一个块端点到块端点的部分可能对答案造成的影响

以前的OI界传统做法是搞一个值域分块，然后每次 $O( 1 )$ 查询一个数在一个区间中出现次数

但是我们的问题实际上比这个弱很多——我们只需要 $O( 1 )$ check if这个数在这个区间中出现次数为ans+1即可

对每个值开一个vector，按顺序维护这个值的所有下标

假设现在在check x，然后x在其的vector的y位置，然后我们只需要check if 这个vector的y-ans,y+ans位置在我们查询的区间 $[l,r]$ 内即可

由于分块每次要向两个方向跑，所以其实只用check一边

这个做法比之前的做法空间，常数，以及代码复杂度都小了很多，可谓是分块之鉴

P.S：

对于问题1,2，我们目前不知道是否达到了下界，如果大家有了解这个的可以在评论区说一下

对于问题3可以去看range mode query的wiki，上面的论文说有strong evidence suggest这个东西是下界了

2019.9.5 update：其实我们在半年前就做出了$O( n^{1.41} )$的区间逆序对，但是8.30被别人先挂了arxiv，所以也没什么意义了吧

2020.4.2 update：看到一篇arxiv上$O( n^{1.4851} )$的区间众数

OldDriverTree的博客