一类区间分治技巧

对于一类区间询问问题,如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去,当前区间[l , r]中点为mid,那么我们将所有的询问分成三类,一类包括mid这个点,一类完全在左侧,一类完全在右侧,我们只要在当前这层解决第一类的所有询问,后两类分治下去即可。怎么快速的求呢?方法也非常简单,因为信息可以快速合并,那么我们以mid为界,往前处理出所有后缀信息,往后处理出所有前缀信息,对于一个跨过mid的询问,拿两部分拼一下就算出答案了!

比在线算法优秀的地方在于可以优雅的去掉询问数所乘的log。

练习题目

1.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest J. Subsequence Sum Queries

考虑背包dp,如果用普通的线段树,时间复杂度\(O((n+q)m^2logn)\),因为拆成logn个区间,要完全合并两个背包log次,合并一次(循环卷积)复杂度是\(O(m^2)\),必T无疑。用优秀的分治就可以降到\(O(m(nlogn+q))\)。

2.2018 Multi-University Training Contest 3 Problem J. Rectangle Radar Scanner 

对x轴分治,对于y用线段树维护一下就好了

时间复杂度\(O(nlog^2n+mlogn)\)