整体二分专题

标签：二分 ch int tr 整体 mid 专题 ql

一、在一个数列中查询第\(k\)小的数

思考一下，如果一个静态的不变化数组，让我们找出第\(k\)小的数，我们用什么办法呢？

① 直接排序，然后\(a[k]\)就是,真暴力
② 使用手动快排，每次排除一半，\(AcWing\) \(786\) 第\(k\)个数这个肯定比上面的那个优秀一些，因为每次排除一半嘛
③不排序，通过二分+暴力枚举本区间内有多少个数小于等于\(mid\)
二分值域，比如\(1e9\)的上限，我们就求\(mid=0+1e9 >>1\),然后，遍历一遍\([0,mid]\),\([mid+1,1e9]\),分别计算一下左侧有多少个值小于\(mid\)的，如果数量小于\(k\)，则放弃右侧，继续二分左侧，...。随着\(mid\)的不断缩放，必然能够找到一个合适的值，使得\(mid=第k个小的数\),此时\(l=r\),取\(l\)值即可。
时间复杂度：\(O(Nlog(1e9))\)

二分mid+暴力枚举每个数字 ,代码略

④不排序，通过二分+树状数组来进行查找第\(k\)小
将每个数字，当作下标位置，到树状数组中标识\(+1\),然后利用区间和+二分答案，如果假设的\(mid\)左侧有\(>=k\)个数，则向左二分，否则向右二分。这个作法是后面扩展的基础，不理解不要继续研究。
时间复杂度：\(O(logN \times log(1e9))\)

整体第\(k\)小

#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\)了，则结束这个部分的二分。

整体二分能够帮助你不用写各种树套主席树(动态第\(k\)小的数，也就是一边查询一边修改，需要用树状数组+主席树解决,传说中的树套树) 就能很轻易地求出第\(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\)

#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\)

#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\)大数查询

#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;
}