【基于归并排序的分治】统计问题

时间:2021-09-22 04:05:33

题目是这样的:给你一个N*N的矩阵,可以完成两个操作

      1.修改某个格子的权值;2.查询某个矩形的权值。

 

看到题目以后很快想到的是二维树状数组,但是N<500000;Q<200000;空间上显然承受不了,第二个选择就是二维动态线段树,弊端是编程复杂度大,常数大,估计写出来是不可能的了。。。

 

不过既然有这种题目,那么就一定是有解决办法的,在线算法不行,可以考虑离线算法,这个离线算法应该怎么做呢?

深入考虑这道题,发现他相当于是要满足在3个偏序集的基础上进行统计---时间、x坐标、y坐标,怎样才可以满足条件呢?对于2个偏序集,我们常用的方法是对其中某一个偏序集进行排序使其成为全序集,再用数据结构统计另一个偏序集。3个应该怎么办?

 

(看了题解后)应该还记得经典的统计逆序对的算法吧-有两种做法,基于算法的归并排序,基于数据结构的树状数组,逆序对就是2个偏序集,如果归并排序加上树状数组能不能维护3个偏序集呢?答案是肯定的!

 

根据刚才的思想我们便设计出了一个非常漂亮的算法,对于一段区间[l,r](时间)上的操作,我递归成[l,m],[m+1,r]那么现在我们现在还没有统计的就是[l,m]中的1操作对[m+1,r]中的2操作的影响,我们便把它们单独拿出来算一遍就可以了(按x排好序,对y用树状数组统计)。

 

复杂度为O(QlogQlogN),归并排序和树状数组都属于常数非常小的算法,所以500000的数据只要1S,总之这是个非常漂亮的算法!

 

编程复杂度极低: