UOJ Logo OldDriverTree的博客

博客

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

2018-11-20 19:52:35 By OldDriverTree

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

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

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

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

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

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

可以在这里提交https://www.luogu.org/problemnew/show/P5046

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 )$ 的空间的

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

可以在这里提交https://www.luogu.org/problemnew/show/P5047

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一边

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

可以在这里提交https://www.luogu.org/problemnew/show/P5048

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} )$的区间众数

评论

owenowl
先膜为敬
Ycrpro
先膜为敬 神O
falun
**神O**
negiizhao
是用纯组合方法的话,预处理和查询中不能避免 $O(\sqrt n)$ 因子吧
kczno1
orz
kczno1
感觉区间众数这个做法很简单,却从来没有人写过。。
duliu
三道经典毒瘤题的更差复杂度解法
newbie314159
先膜神O为敬
hqztrue
关于第三个问题,range mode query的wiki上引用我老板的结果有点偏差啊...现在可以做到O(sqrt(n/log n))单次询问。
MVP_Bxbl
先膜为敬 顺便吐槽一下毒瘤
1942938446
神·lxl ! tql!%%%
disangan233
LaTeX 炸了
happydef
是 O(sqrt(n)) 插入,O(1) 查询的数据结构吧
DPair
lxl Orz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。