536 lines
18 KiB
Markdown
536 lines
18 KiB
Markdown
## 整体二分专题
|
||
|
||
[视频讲解](https://www.bilibili.com/video/BV1LC4y1x73c/?vd_source=13b33731bb79a73783e9f2c0e11857ae)
|
||
|
||
[$oiwiki$参考资料](https://oi-wiki.org/misc/parallel-binsearch/)
|
||
|
||
### 一、在一个数列中查询第$k$小的数
|
||
[$POJ2104$ $K-th$ $Number$](http://poj.org/problem?id=2104)
|
||
|
||
思考一下，如果一个静态的不变化数组，让我们找出第$k$小的数，我们用什么办法呢？
|
||
|
||
* ① 直接排序，然后$a[k]$就是,真暴力
|
||
|
||
* ② 使用手动快排，每次排除一半，[$AcWing$ $786$ 第$k$个数](https://www.acwing.com/problem/content/788/) 这个肯定比上面的那个优秀一些，因为每次排除一半嘛
|
||
|
||
* ③不排序，通过二分+暴力枚举本区间内有多少个数小于等于$mid$
|
||
二分值域，比如$1e9$的上限，我们就求$mid=0+1e9 >>1$,然后，遍历一遍$[0,mid]$,$[mid+1,1e9]$,分别计算一下左侧有多少个值小于$mid$的，如果数量小于$k$，则放弃右侧，继续二分左侧，...。随着$mid$的不断缩放，必然能够找到一个合适的值，使得$mid=第k个小的数$,此时$l=r$,取$l$值即可。
|
||
**时间复杂度**：$O(Nlog(1e9))$
|
||
```cpp {.line-numbers}
|
||
二分mid+暴力枚举每个数字 ,代码略
|
||
```
|
||
|
||
* ④不排序，通过二分+树状数组来进行查找第$k$小
|
||
将每个数字，当作下标位置，到树状数组中标识$+1$,然后利用区间和+二分答案，如果假设的$mid$左侧有$>=k$个数，则向左二分，否则向右二分。这个作法是后面扩展的基础，不理解不要继续研究。
|
||
**时间复杂度**：$O(logN \times log(1e9))$
|
||
|
||
**整体第$k$小**
|
||
```cpp {.line-numbers}
|
||
#include <iostream>
|
||
#include <algorithm>
|
||
#include <cstring>
|
||
using namespace std;
|
||
const int N = 1025;
|
||
|
||
//快读
|
||
int read() {
|
||
int x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
|
||
//树状数组
|
||
int tr[N];
|
||
void add(int x, int c) {
|
||
for (; x < N; x += x & -x) tr[x] += c;
|
||
}
|
||
//查询x的个数和
|
||
int getSum(int x) {
|
||
int sum = 0;
|
||
for (; x; x -= x & -x) sum += tr[x];
|
||
return sum;
|
||
}
|
||
|
||
//从1开始查找第k小的数
|
||
int getKth(int k) {
|
||
int l = 1, r = N - 1; //保证数组不能越界
|
||
while (l < r) {
|
||
int mid = (l + r) >> 1;
|
||
if (getSum(mid) >= k)
|
||
r = mid;
|
||
else
|
||
l = mid + 1;
|
||
}
|
||
return l;
|
||
}
|
||
/*
|
||
测试用用例:
|
||
2 9 1 3 12 7 6 -1
|
||
3
|
||
|
||
答案：
|
||
3
|
||
*/
|
||
int main() {
|
||
int x;
|
||
while (x = read(), ~x) add(x, 1); // x这个位置上+1
|
||
int k = read();
|
||
printf("%d\n", getKth(k));
|
||
return 0;
|
||
}
|
||
```
|
||
### 二、在一个数列中 多次 查询第$k$小的数
|
||
但事情往往没有那么简单，比如：
|
||
* ⑤ **在一个数列中多次查询第$k$小的数**
|
||
|
||
求一个序列的第k大，显然可以采取二分解决，但当询问量较大时，我们无法承受每次询问都二分一遍的时间消耗，可以把所有的询问放在一起二分。
|
||
|
||
对于当前的所有询问，可以去猜测所有询问的答案都是$mid$，然后去依次验证每个询问的答案应该是小于等于$mid$的还是大于$mid$的，并将询问分为两个部分（小于等于/大于），对于每个部分继续二分。注意：如果一个询问的答案是大于$mid$的，则在将其划至右侧前需更新它的$k$ ，即，如果当前数列中小于等于 $mid$ 的数有 $t$ 个，则将询问划分后实际是在右区间询问第 $k-t$ 小数。如果一个部分的$l=r$了，则结束这个部分的二分。
|
||
|
||
|
||
整体二分能够帮助你不用写各种**树套主席树**(<font color='red' size=3><b>动态第$k$小的数，也就是一边查询一边修改，需要用树状数组+主席树解决,传说中的树套树</b></font>) 就能很轻易地求出第$k$小数。
|
||
|
||
首先确定一个决策区间$solve(l, r, ql, qr)$表示编号在$ql\sim qr$的操作的数的权值和询问的答案在$l\sim r$这个区间，每次将答案二分，把$ql\sim qr$里的修改操作按被修改数的权值$<=mid$和$>mid$分成左右两边，如果$<=mid$，就把它下标所在位置在树状数组里$+1$，把$ql\sim qr$里的查询操作按树状数组上查询区间里的$t>=k$和$t<k$分成左右两边，如果$t<k$，那么$k$就要减去树状数组上查询区间里的$t$，然后就按丢到左右两边的操作分治就好了。
|
||
|
||
应该还是不难理解的，虽然将操作和询问分成左右两边修改了原顺序，但是会互相影响的操作之间一定是按原顺序进行的，因为修改的排名大的数对排名小的数无影响，先处理答案小的，所以处理答案大的时候$k$已经减去了答案小的时候的贡献，于是处理答案大的区间的时候实际也不受到答案小的区间的影响，这样就能做到一层$O(N)$，一共$log(N)$层，加上树状数组复杂度$log(N)$，总复杂度$O(Nlog^2N)$。
|
||
|
||
**无修改，区间$[l,r]$之内多次查询第$k$小** [整体二分解法]
|
||
[$P3834$ 【模板】可持久化线段树 $2$](https://www.luogu.com.cn/problem/P3834)
|
||
|
||
```cpp {.line-numbers}
|
||
#include <algorithm>
|
||
#include <cstdio>
|
||
#include <cmath>
|
||
#include <cstring>
|
||
using namespace std;
|
||
//快读
|
||
int read() {
|
||
int x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
const int N = 400010;
|
||
int n, m;
|
||
int a[N]; //维护的序列
|
||
int ans[N]; // 结果
|
||
|
||
struct Node {
|
||
// op=1 插入, op=-1 删除, op=2 查询
|
||
int op;
|
||
// 插入：l:插入的值,用于二分与mid PK,r:位置
|
||
// 删除：l:删除的值,用于二分与mid PK,r:位置
|
||
// 查询 [l,r]：查询范围
|
||
// k:第k小
|
||
int l, r, k;
|
||
int id;
|
||
} q[N], lq[N], rq[N];
|
||
|
||
//树状数组
|
||
int tr[N];
|
||
void add(int x, int c) {
|
||
for (; x < N; x += x & -x) tr[x] += c;
|
||
}
|
||
//查询x的个数和
|
||
int getSum(int x) {
|
||
int sum = 0;
|
||
for (; x; x -= x & -x) sum += tr[x];
|
||
return sum;
|
||
}
|
||
|
||
void solve(int l, int r, int ql, int qr) {
|
||
if (ql > qr) return; //防止RE，递归边界
|
||
|
||
if (l == r) { //递归到叶子结点，找到答案
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 2) ans[q[i].id] = l; //所有查询请求，标识答案
|
||
return;
|
||
}
|
||
|
||
int mid = (l + r) >> 1;
|
||
int nl = 0, nr = 0;
|
||
|
||
for (int i = ql; i <= qr; i++) {
|
||
if (q[i].op < 2) {
|
||
//插入、删除操作二分
|
||
if (q[i].l <= mid)
|
||
add(q[i].r, q[i].op), lq[++nl] = q[i]; //根据q[i].op的不同，通过一样的add函数，在位置q[i].r处，完成插入+1，删除-1的操作
|
||
else
|
||
rq[++nr] = q[i];
|
||
} else {
|
||
//查询数组二分
|
||
int t = getSum(q[i].r) - getSum(q[i].l - 1);
|
||
if (q[i].k <= t)
|
||
lq[++nl] = q[i];
|
||
else {
|
||
q[i].k -= t;
|
||
rq[++nr] = q[i];
|
||
}
|
||
}
|
||
}
|
||
|
||
// 有借有还，再借不难
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op < 2)
|
||
if (q[i].l <= mid) add(q[i].r, -q[i].op);
|
||
|
||
for (int i = 1; i <= nl; i++) q[ql - 1 + i] = lq[i]; //将左儿子操作数组，拷贝到q中，原来的下标是[0~ql-1],现在无缝接上[ql-1+1~ql-1+nl]
|
||
for (int i = 1; i <= nr; i++) q[ql - 1 + nl + i] = rq[i]; //将右儿子操作数组，拷贝到q中，原来的下标是[ql-1+nl+i]
|
||
|
||
//继续二分左右儿子
|
||
solve(l, mid, ql, ql + nl - 1), solve(mid + 1, r, ql + nl, qr);
|
||
}
|
||
|
||
int main() {
|
||
int l, r, k, c = 0, qc = 0;
|
||
n = read(), qc = read();
|
||
for (int i = 1; i <= n; i++) a[i] = read(), q[++c] = {1, a[i], i}; // op=1:插入,a[i]:值，i:位置
|
||
|
||
for (int i = 1; i <= qc; i++) {
|
||
l = read(), r = read(), k = read();
|
||
q[++c] = {2, l, r, k, i}; // op=2：查询,[l,r]:查询范围,k:第k小,i:查询序号
|
||
}
|
||
//整体二分
|
||
solve(-1e9, 1e9, 1, c); //值域[-1e9,1e9],二分查询区间[1,n+m]
|
||
|
||
//结果
|
||
for (int i = 1; i <= qc; i++) printf("%d\n", ans[i]);
|
||
return 0;
|
||
}
|
||
|
||
```
|
||
|
||
**单点修改+区间$[l,r]$之内多次查询第$k$小**
|
||
[$P2617$ $Dynamic$ $Rankings$](https://www.luogu.com.cn/problem/P2617)
|
||
|
||
```cpp {.line-numbers}
|
||
#include <algorithm>
|
||
#include <cstdio>
|
||
#include <cmath>
|
||
#include <cstring>
|
||
using namespace std;
|
||
//快读
|
||
int read() {
|
||
int x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
|
||
const int N = 300010;
|
||
int n, m;
|
||
int a[N]; //维护的序列
|
||
int ans[N]; // 结果
|
||
|
||
struct Node {
|
||
// op=1 插入, op=-1 删除, op=2 查询
|
||
int op;
|
||
// 插入：l:插入的值,用于二分与mid PK,r:位置
|
||
// 删除：l:删除的值,用于二分与mid PK,r:位置
|
||
// 查询 [l,r]：查询范围
|
||
// k:第k小
|
||
int l, r, k;
|
||
int id;
|
||
} q[N], lq[N], rq[N];
|
||
|
||
//树状数组
|
||
int tr[N];
|
||
void add(int x, int c) {
|
||
for (; x < n; x += x & -x) tr[x] += c;
|
||
}
|
||
//查询x的个数和
|
||
int getSum(int x) {
|
||
int sum = 0;
|
||
for (; x; x -= x & -x) sum += tr[x];
|
||
return sum;
|
||
}
|
||
|
||
void solve(int l, int r, int ql, int qr) {
|
||
if (ql > qr) return; //防止RE，递归边界
|
||
|
||
if (l == r) { //递归到叶子结点，找到答案
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 2) ans[q[i].id] = l; //所有查询请求，标识答案
|
||
return;
|
||
}
|
||
|
||
int mid = (l + r) >> 1;
|
||
int nl = 0, nr = 0;
|
||
|
||
for (int i = ql; i <= qr; i++) {
|
||
if (q[i].op < 2) { // 非查询，插入:1 或 删除:-1
|
||
if (q[i].l <= mid) //按插入、删除的值与mid相对比进行左右决策
|
||
add(q[i].r, q[i].op), lq[++nl] = q[i]; //位置是q[i].r,如果是插入，则+1,如果是删除则-1
|
||
else
|
||
rq[++nr] = q[i];
|
||
} else {
|
||
//查询数组二分
|
||
int t = getSum(q[i].r) - getSum(q[i].l - 1);
|
||
if (q[i].k <= t)
|
||
lq[++nl] = q[i];
|
||
else {
|
||
q[i].k -= t;
|
||
rq[++nr] = q[i];
|
||
}
|
||
}
|
||
}
|
||
|
||
// 有借有还，再借不难
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op < 2)
|
||
if (q[i].l <= mid) add(q[i].r, -q[i].op);
|
||
|
||
for (int i = 1; i <= nl; i++) q[ql - 1 + i] = lq[i]; //将左儿子操作数组，拷贝到q中，原来的下标是[0~ql-1],现在无缝接上[ql-1+1~ql-1+nl]
|
||
for (int i = 1; i <= nr; i++) q[ql - 1 + nl + i] = rq[i]; //将右儿子操作数组，拷贝到q中，原来的下标是[ql-1+nl+i]
|
||
|
||
//继续二分左右儿子
|
||
solve(l, mid, ql, ql + nl - 1), solve(mid + 1, r, ql + nl, qr);
|
||
}
|
||
|
||
int main() {
|
||
int l, r, k, c = 0, qc = 0; // c:总的操作次数，qc:查询次数
|
||
n = read(), m = read();
|
||
for (int i = 1; i <= n; i++) a[i] = read(), q[++c] = {1, a[i], i}; // op=1:插入,a[i]:值(用于与mid进行决策左右前进)，i:位置
|
||
|
||
char op[2];
|
||
for (int i = 1; i <= m; i++) {
|
||
scanf("%s", op);
|
||
if (op[0] == 'Q') {
|
||
l = read(), r = read(), k = read();
|
||
q[++c] = {2, l, r, k, ++qc}; // op=2:查询,[l,r]:区间,k:第k小，++qc:查询的个数
|
||
} else {
|
||
int x = read(), y = read(); //修改操作
|
||
q[++c] = {-1, a[x], x}; // op=-1:删除,数值:a[x],位置:x
|
||
q[++c] = {1, y, x}; // op=1:插入,数值：y,位置:x
|
||
a[x] = y; //因为a[x]上面有用，所以只能用y临时读入一下，再更新a[x],因为可能存在重复修改，a[x]必须更新
|
||
}
|
||
}
|
||
//整体二分
|
||
solve(-1e9, 1e9, 1, c);
|
||
|
||
//结果
|
||
for (int i = 1; i <= qc; i++) printf("%d\n", ans[i]);
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**区间修改+整体二分+线段树**
|
||
[$P3332$ [$ZJOI2013$]$K$大数查询](https://www.luogu.com.cn/problem/P3332)
|
||
|
||
2023.1.5 本题是不是也可以不用线段树，而是用树状数组+差分来解决，现在没有时间，下次再刷过来时仔细研究吧~！
|
||
|
||
```cpp {.line-numbers}
|
||
#include <algorithm>
|
||
#include <iostream>
|
||
#include <cstring>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
//快读
|
||
LL read() {
|
||
LL x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
const int N = 200010;
|
||
|
||
LL ans[N]; //每个询问的答案
|
||
int n, m; //原始n个数字，共m个操作
|
||
|
||
//线段树结构体
|
||
#define ls u << 1
|
||
#define rs u << 1 | 1
|
||
struct Node {
|
||
int l, r; //区间范围
|
||
LL lazy; //区间修改懒标记
|
||
LL sum; //区间和
|
||
} tr[N << 2];
|
||
|
||
//向上更新统计信息:区间和
|
||
void pushup(int u) {
|
||
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
||
}
|
||
|
||
//向下传递区间修改标记
|
||
void pushdown(int u) {
|
||
//如果懒标记为0,没有可以传递
|
||
if (!tr[u].lazy) return;
|
||
|
||
//向下传递lazy标志
|
||
tr[ls].lazy += tr[u].lazy, tr[rs].lazy += tr[u].lazy; //加法有叠加性
|
||
|
||
//用lazy通过计算，更新左右儿子的sum值
|
||
int l = tr[u].l, r = tr[u].r;
|
||
int mid = (l + r) >> 1;
|
||
tr[ls].sum += tr[u].lazy * (mid - l + 1);
|
||
tr[rs].sum += tr[u].lazy * (r - mid);
|
||
|
||
// lazy标记清零
|
||
tr[u].lazy = 0;
|
||
}
|
||
|
||
//构建线段树
|
||
void build(int u, int l, int r) {
|
||
tr[u] = {l, r, 0, 0};
|
||
if (l == r) return;
|
||
int mid = (l + r) >> 1;
|
||
build(ls, l, mid), build(rs, mid + 1, r);
|
||
}
|
||
|
||
//区间更新
|
||
//之所以参数起名为[ql,qr]因为这是查询区间，而不是构建区间
|
||
void modify(int u, int ql, int qr, LL c) {
|
||
int l = tr[u].l, r = tr[u].r; //将变量名l,r保留下来给tr[u].l,tr[u].r
|
||
if (ql <= l && qr >= r) { // u结点的管辖范围[tr[u].l~tr[u].r]完整命中
|
||
tr[u].lazy += c; //区间修改加上lazy标记,这样就不用现在就逐层下传了
|
||
tr[u].sum += c * (r - l + 1); //对统计信息进行更新,完成本层的统计信息更新
|
||
return;
|
||
}
|
||
|
||
//下面要进行分裂，分裂前需要pushdown
|
||
pushdown(u);
|
||
|
||
int mid = (l + r) >> 1;
|
||
if (ql <= mid) modify(ls, ql, qr, c); //与左儿子区间有交集，递归左儿子
|
||
if (mid < qr) modify(rs, ql, qr, c); //与右儿子区间有交集，递归右儿子
|
||
|
||
//向上更新统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//查询区间sum和
|
||
LL query(int u, int ql, int qr) {
|
||
int l = tr[u].l, r = tr[u].r;
|
||
if (ql <= l && r <= qr) return tr[u].sum; //完整命中，返回区间和
|
||
|
||
LL res = 0;
|
||
//分裂前需要pushdown
|
||
pushdown(u);
|
||
int mid = (l + r) >> 1;
|
||
if (ql <= mid) res += query(ls, ql, qr); //与左儿子区间有交集，递归左儿子
|
||
if (mid < qr) res += query(rs, ql, qr); //与右儿子区间有交集，递归右儿子
|
||
return res;
|
||
}
|
||
|
||
//整体二分的查询结构体
|
||
struct Q {
|
||
int op, l, r;
|
||
LL k;
|
||
int id;
|
||
} q[N], q1[N], q2[N];
|
||
|
||
//整体二分
|
||
void solve(int l, int r, int ql, int qr) {
|
||
if (ql > qr) return; //无效查询区间，防RE
|
||
|
||
if (l == r) {
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 2) ans[q[i].id] = l; //二分标识答案
|
||
return;
|
||
}
|
||
|
||
int mid = (l + r) >> 1;
|
||
int nl = 0, nr = 0;
|
||
for (int i = ql; i <= qr; i++) {
|
||
if (q[i].op == 1) { //增加
|
||
if (q[i].k > mid) {
|
||
modify(1, q[i].l, q[i].r, 1); //用线段树指定区全都+1
|
||
q1[++nl] = q[i]; //加入左增加操作
|
||
} else
|
||
q2[++nr] = q[i]; //加入右增加操作
|
||
} else { //查询
|
||
LL t = query(1, q[i].l, q[i].r);
|
||
if (t >= q[i].k)
|
||
q1[++nl] = q[i];
|
||
else {
|
||
q[i].k -= t;
|
||
q2[++nr] = q[i];
|
||
}
|
||
}
|
||
}
|
||
//有加就有减
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 1)
|
||
if (q[i].k > mid) modify(1, q[i].l, q[i].r, -1);
|
||
|
||
//合并到q数组
|
||
for (int i = ql; i < ql + nl; i++) q[i] = q1[i - ql + 1];
|
||
for (int i = ql + nl; i <= qr; i++) q[i] = q2[i - ql - nl + 1];
|
||
|
||
//递归左右
|
||
solve(mid + 1, r, ql, ql + nl - 1), solve(l, mid, ql + nl, qr);
|
||
}
|
||
int main() {
|
||
//原序列n个数字，共m个操作
|
||
n = read(), m = read();
|
||
|
||
//构建线段树
|
||
build(1, 1, n);
|
||
|
||
int qc = 0; //查询的个数
|
||
for (int i = 1; i <= m; i++) {
|
||
int op = read(), l = read(), r = read(), k = read();
|
||
if (op == 2) //查询操作
|
||
q[i] = {op, l, r, k, ++qc};
|
||
else // 增加操作 op=1
|
||
// 1 l r k : op=1 增加，[l,r]:增加k
|
||
q[i] = {op, l, r, k};
|
||
}
|
||
|
||
//整体二分
|
||
solve(-1e9, 1e9, 1, m);
|
||
|
||
//输出
|
||
for (int i = 1; i <= qc; i++) printf("%lld\n", ans[i]);
|
||
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 三、参考资料
|
||
https://blog.csdn.net/qq_35975367/article/details/116722196
|
||
https://blog.csdn.net/qq_35975367/article/details/116740190
|
||
|
||
|
||
### 四、待完成试题TODO
|
||
[P1533 可怜的狗狗](https://www.luogu.com.cn/problem/solution/P1533)
|
||
|
||
[P3527[POI2011]MET-Meteors](https://www.luogu.com.cn/problem/P3527)
|
||
https://blog.csdn.net/weixin_45750972/article/details/119103938
|
||
|
||
[P1527 [国家集训队]矩阵乘法](https://www.luogu.com.cn/problem/P1527)
|
||
https://blog.csdn.net/qq_35975367/article/details/116748509
|
||
|
||
[P7424 [THUPC2017] 天天爱射击](https://www.luogu.com.cn/problem/P7424)
|
||
|