python

18 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

整体二分专题

视频讲解

oiwiki参考资料

一、在一个数列中查询第`k`小的数

POJ2104 K-th Number

思考一下，如果一个静态的不变化数组，让我们找出第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大数查询

2023.1.5 本题是不是也可以不用线段树，而是用树状数组+差分来解决，现在没有时间，下次再刷过来时仔细研究吧~！

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