ConanKIDの小窝

ConanKIDの小窝

整体二分学习笔记

posted on 2021-08-23 14:40:04 | under 学习笔记 |

整体二分,数据结构题的一种非数据结构解法。


来看题

一道很经典的题目——区间静态第 $k$ 小,其解法也多种多样。

对于每个询问 $(l,r,k)$,考虑二分答案。设当前二分的值为 $mid$,我们求出区间 $[l,r]$ 内小于等于 $mid$ 的数的个数 $x$。如果 $x\ge k$,就证明答案小于等于 $mid$;否则,答案大于 $mid$。但这样做的总时间复杂度是 $O(nm\log SIZE)$,无法承受。($SIZE$ 表示值域)

注意到对于每个询问,我们二分的 $mid$ 都是相同的,那么可不可以把所有询问放在一起二分呢?

具体来说,我们执行以下流程:

  1. 把所有询问离线下来;
  2. 二分答案 $mid$,把序列 $a$ 中所有小于等于 $mid$ 的数设为 $1$;
  3. 利用树状数组,统计第 $i$ 个询问区间中小于等于 $mid$ 的数的数量,从而确定这个询问的答案与 $mid$ 的大小关系;
  4. 递归求解所有答案小于等于 $mid$ 的询问;
  5. 递归求解所有答案大于 $mid$ 的询问。(这样一来,原问题就被划分成了两个规模更小的子问题,可以继续递归)

为了方便,我们可以把序列中的第 $i$ 个数看成修改操作。如果修改的数,即 $a_i\le mid$,就把这个操作划到答案小于等于 $mid$ 的询问的集合里;否则,划到答案大于 $mid$ 的询问的集合里。

需要注意,树状数组清零不能用memset,要把所有修改操作逐一撤销掉,否则复杂度会爆炸。

#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f == 1 ? x : -x;
}
inline void update(int x, int val) {
    for (; x <= n; x += x & -x)
        sum[x] += val;
}
inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += sum[x];
    return res;
}
inline void solve(int l, int r, int st, int ed) {//l,r表示答案的值域区间,st,ed表示询问的区间
    if (st > ed) return;
    if (l == r) {
        for (int i = st; i <= ed; ++i)
            if (q[i].p == 2) ans[q[i].id] = l;
        return;
    } 
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    //lq存储所有答案<=mid的询问,rq存储答案>mid的询问
    for (int i = st; i <= ed; ++i) {
        if (q[i].p == 1) {//修改操作
            if (q[i].y <= mid) update(q[i].x, 1), lq[++cnt1] = q[i];
            else rq[++cnt2] = q[i];
        } else {//询问操作
            int x = query(q[i].y) - query(q[i].x - 1);
            if (x >= q[i].k) lq[++cnt1] = q[i];
            else q[i].k -= x, rq[++cnt2] = q[i];
            //如果一个询问的答案大于mid,那么划分后实际上是在找第k-x小数
        }
    }
    for (int i = st; i <= ed; ++i)
        if (q[i].p == 1 && q[i].y <= mid) update(q[i].x, -1);//撤销所有修改
    for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
    for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];//把两组询问copy回原数组,防止空间爆炸
    solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);//递归求解
}
int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++)
        q[i] = (node){1, i, read(), 0, 0};
    for (int i = 1; i <= m; i++) 
        q[i + n] = (node){2, read(), read(), read(), i};//把询问离线下来操作
    solve(-1e9, 1e9, 1, n + m);
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

来分析一波时间复杂度。每个询问会被递归 $\log SIZE$ 层,而一个操作每次递归都会在树状数组中被 $\log n$ 地更新一次,算上修改我们一共有 $n+m$ 个操作,因此总时间复杂度为 $O((n+m)\log n\log SIZE)$。

顺带提一嘴 $O(n\log n)$ 的神仙做法:把所有修改操作按 $a_i$ 排个序;把所有询问 $[l,r]$ 拆成 $[1,l-1]$ 和 $[1,r]$,再把拆出来的区间按照右端点排个序。于是我们求 $[l,r]$ 内有多少个数小于等于 $mid$ 时,就只需要一个指针扫过去就可以了。这样就做到了单个 $\log$。代码就不给了,更加详细的分析可以看这篇 blog


接下来是这个

与上一题相比,只是从静态变为了动态。但是如果直接按照题意修改的话,我们将需要面临这个数原本是否大于 $mid$、修改后是否大于 $mid$ 等多种情况分类讨论,增加了码长还容易写挂。因此,我们需要把一次修改看成两次操作,即在位置 $x$ 上去掉了一个值为 $a_x$ 的数,又增加了一个值为 $y$ 的数。于是这样我们就不需要分情况讨论了。

P.S.:读入修改操作时,必须把 $a_x$ 赋值为 $y$,正确维护 $a$ 序列,否则只有 $5$ 分——这是血的教训!

#include<bits/stdc++.h>
using namespace std;
int n, m;
int t, cnt;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return f == 1 ? x : -x;
}
inline void update(int x, int val) {
    for (; x <= n; x += x & -x)
        sum[x] += val;
}
inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += sum[x];
    return res;
}
inline void solve(int l, int r, int st, int ed) {
    if (st > ed) return;
    if (l == r) {
        for (int i = st; i <= ed; ++i)
            if (q[i].p == 1) ans[q[i].id] = l;
        return;
    } 
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (int i = st; i <= ed; ++i) {
        if (q[i].p == 0) {
            if (q[i].y <= mid) update(q[i].x, q[i].k), lq[++cnt1] = q[i];
            else rq[++cnt2] = q[i];
        } else {
            int x = query(q[i].y) - query(q[i].x - 1);
            if (x >= q[i].k) lq[++cnt1] = q[i];
            else q[i].k -= x, rq[++cnt2] = q[i];
        }
    }
    for (int i = st; i <= ed; ++i)
        if (q[i].p == 0 && q[i].y <= mid) update(q[i].x, -q[i].k);
    for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
    for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];
    solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}//同样的方法求解
int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        q[++t] = (node){0, i, a[i], 1, 0};
    }
    for (int i = 1; i <= m; ++i) {
        char c; int x, y, k; cin >> c;
        if (c == 'Q') {
            x = read(); y = read(); k = read();
            q[++t] = (node){1, x, y, k, ++cnt};
        } else {
            x = read(); y = read();
            q[++t] = (node){0, x, a[x], -1, 0};
            q[++t] = (node){0, x, y, 1, 0};//把修改分成两个操作
            //结构体中的k表示这是删除还是添加
            a[x] = y;//很重要的一行,我老是忘
        }
    }//必须要把所有操作按时间顺序存进数组
    solve(-1e9, 1e9, 1, t);
    for (int i = 1; i <= cnt; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

与树套树相比,整体二分的理论复杂度从 $O((n+m)\log^2n)$ 变成了 $O((n+m)\log n\log SIZE)$,但看看实际效果:

算法 线段树套平衡树 整体二分
时间 $23.23s$ $2.06s$
空间 $88.13MB$ $21.09MB$
码长 $2.77KB$ $1.90KB$

可以发现,整体二分无论是从哪个方面都吊打了树套树。树状数组套主席树我没写过,不过从其他人的提交记录来看应该也是跑不过整体二分的。


几道练习:


接下来是整体二分的综合运用,它不止能做区间 Kth 问题。

这道题开始变形了

我们依旧可以进行整体二分,看在第 $[l,mid]$ 场陨石雨过后,第 $i$ 个国家是否收集到了足够的陨石,从而确定答案与 $mid$ 的大小关系。

此题还需要判断无解。我们不需要多花精力去特判,可以人为地加上第 $k+1$ 场陨石雨。这样一来,无解的询问在二分时就会一直向右递归,答案就会变成 $k+1$,就很好判断了。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, m, k;
vector<int> o[300005];
struct option {int l, r, k;} a[300005];
struct node {int p, k;} q[300005], lq[300005], rq[300005];
int sum[300005], ans[300005];
int lowbit(int x) {return x & -x;}
void update(int x, int val) {
    for (; x <= m; x += lowbit(x))
        sum[x] += val;
}
int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += sum[x];
    return res;
}
void solve(int l, int r, int st, int ed) {
    if (st > ed) return;
    if (l == r) {
        for (int i = st; i <= ed; i++)
            ans[q[i].p] = l;
        return;
    }
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (int i = l; i <= mid; i++)
        if (a[i].l <= a[i].r) update(a[i].l, a[i].k), update(a[i].r + 1, -a[i].k);
        else update(a[i].l, a[i].k), update(1, a[i].k), update(a[i].r + 1, -a[i].k);
    for (int i = st; i <= ed; i++) {
        int s = 0;
        for (int j = 0; j < o[q[i].p].size(); j++)
            s += query(o[q[i].p][j]);
        if (q[i].k <= s) lq[++cnt1] = q[i];
        else q[i].k -= s, rq[++cnt2] = q[i];
    }
    for (int i = l; i <= mid; i++)
        if (a[i].l <= a[i].r) update(a[i].l, -a[i].k), update(a[i].r + 1, a[i].k);
        else update(a[i].l, -a[i].k), update(1, -a[i].k), update(a[i].r + 1, a[i].k);
    for (int i = 1; i <= cnt1; i++) q[st + i - 1] = lq[i];
    for (int i = 1; i <= cnt2; i++) q[st + cnt1 + i - 1] = rq[i];
    solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        o[x].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> q[i].k, q[i].p = i;
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i].l >> a[i].r >> a[i].k;
    a[k + 1] = (option){1, m, 0};//为了判断无解,加上第k+1次陨石雨
    solve(1, k + 1, 1, n);
    for (int i = 1; i <= n; i++)
        if (ans[i] == k + 1) cout << "NIE" << endl;
        else cout << ans[i] << endl;
    return 0;
}

几道习题:


最后套用一下许昊然大佬的论文吧。

可以使用整体二分解决的题目需要满足以下性质:

  1. 询问的答案具有可二分性
  2. 修改对判定答案的贡献互相独立,修改之间互不影响效果
  3. 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值
  4. 贡献满足交换律,结合律,具有可加性
  5. 题目允许使用离线算法

没有了