逃了这么久终究是逃不过
首先我们考虑一个最基础的二维偏序问题,逆序对。
其实质上是求对于有序对$(x,y)$,$x$是其在数组中的位置$y$即他的值,有多少个有序对$(a,b)$,满足$xb$。
而我们可以发现在这个问题中,$x$是默认有序的,因为是从左到右遍历,而对于这个问题,我们可以用树状数组来进行对值域区间查询的优化。
那我们考虑一个树状数组的问题:
给定一个N个元素的序列$a$,初始值全部为0,对这个序列进行以下两种操作
操作1:格式$1\ x\ k$,把位置x的元素加上$k$
操作2:格式为$2\ x\ y$,求出区间$[x,y]$内所有元素的和
我们可以将它考虑成一个二维偏序的问题,$(x,y)$,$x$表示操作的时间,$y$表示操作的位置,考虑归并排序,对于前者是默认有序的,那么在合并的时候,只需要按$y$从小到大合并即可。在计算的时候,我们只更新左半边的1操作和右半边的2操作,而2操作我们可以用前缀和的思想进行更新。
1 | struct node{ |
从上我们可以看出,他将维度进行了降维,即时间,坐标,权值变成了坐标和权值。
那继续看:
这题我们要做的是先进行预处理,合并同类项。
然后和上面的处理方式差不多,先将$a$即第一维排成有序的,然后再按照二维偏序的写法进行统计,同样的我们只更新左边,统计右边。
1 | function<void(int,int)> cdq=[&](int l,int r){ |
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2022/06/15/CDQ分治/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!