Java教程

关于不带修区间逆序对的一些做法

本文主要是介绍关于不带修区间逆序对的一些做法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

离线做法:莫队+树状数组

每次加减考虑贡献即可,时间复杂度: \(\Theta(n\sqrt{n}\log n)\)

在线做法

有三种

第一种

拿个树状数组和主席树乱搞搞,跑的慢而且难写(好像这些东西没有好写的),而且时间复杂度并不优秀,是同样的 \(\Theta(n\sqrt{n}\log n)\)

第二种

虽然时间复杂度依然是 \(\Theta(n\sqrt{n}\log n)\) ,但常数比第一种小而且稍微好写一点。考虑对一个位置提前处理出到每个块的左边界的逆序对的数量,做法是对每个块左边界建树状数组,然后进来一个数,更新所有在范围内的左边界的树状数组,对右边界同理。然后这么一个事实:令 \(a\) 表示 \(l\) 所在的块,\(b\) 表示 \(r\) 所在的块,那么 \(cnt_{left(a),r}+cnt_{l,right(b)}-cnt_{left(a),right(b)}=cnt_{l,r}-cnt_{c,d},c\in[left(a),l-1],d\in[r+1,right(b)]\) ,画个图算算就好了,等式前面我们已经预处理了所有的答案,等式右面的后者,因为都是散块,所以直接暴力树状数组即可。

第三种

时间复杂度是优秀的 \(\Theta(n\sqrt{n})\) ,但不怎么好写。。。

其实并不妙,发现答案可以分解为,散块内部答案,整块内部的答案,散块与散块间的答案,整块与整块间的答案,散块与整块间的答案。

散块内部答案可以提前预处理每个位置到所在块左端的答案,这个东西可以考虑对于每个位置,查一下这个块到现在的树状数组即可,询问的时候问一下就好了。

整块内部答案,和散块内部答案一个样,树状数组即可。

散块与散块间答案,可以提前处理出第 \(i\) 个块中,前 \(j\) 个数,排序后的样子,因为都是 \(\Theta(\sqrt{n})\) 级别的,加上要存这个排列,那么空间复杂度就是 \(\Theta(n\sqrt{n})\) ,至于怎么求出来,我们考虑冒泡排序,因为每个位置最多向前跑 \(\Theta(\sqrt{n})\) ,所以复杂度有保证。查的时候归并即可。

整块与整块间的答案,和散块间答案一个样,排序后归并即可。

散块与整块间答案,考虑一个位置与一个块的答案,我们可以不按顺序来搞,对这个位置所在块进行排序,然后对那个块进行排序,然后一边归并一边更新位置的答案,然后因为散块一定是一个区间,所以你搞个前缀和即可。

这篇关于关于不带修区间逆序对的一些做法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!