整体二分学习笔记

qfpjm · 2022-07-21 20:04:01 · 个人记录

• 校内模拟赛一道题有整体二分的解法，于是就学习了一下。

基本介绍

• 整体二分是一个多次询问区间排名的离线算法，在线二分的时间复杂度为 O(n^2\log n)，但整体二分可以把时间复杂度降到 O(n\log^2 n)。

• 一个题能够使用整体二分需要满足一下几个条件：

1. 答案可以二分；

2. 修改对判定答案的贡献互相独立，修改之间互不影响效果；

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值；

4. 贡献满足交换律，结合律，具有可加性；

5. 题目允许使用离线算法。

• 整体二分大概是一个二分嵌套二分的过程，第一层是把询问的区间分成两类，而分类的界限需要二分来计算。

实现方式

• 整体二分采用递归的方式实现。

• 这里使用询问区间 k 小距离。

• 首先，先存下每个询问，将其排序。

• 然后进入递归，递归函数为：

void solve(int l, int r, vector<Query> q)
// l,r为大值域，q数组为当前在当前这一值域中询问

• 然后判断 l 等不等于 r，如果等于，这类中的答案就是 l 和 r 的值。

• 否则，求出 mid，表示分类的界限。我们将拥有小于等于小于等于 mid 的 k 的询问归到一类，否则规带另一类，继续二分，代码为：

solve(l, m, q1); //q1 是一类
solve(m + 1, r, q2); //q2 是另一类

题目

【模板】可持久化线段树 2

• 这题虽说是主席书模板，但是整体二分才可做，时间复杂度貌似相差不大。

• 显然，我们要优化一下 check 函数，将其改为树状数组即可。