整体二分

发布于 2020-09-26  65 次阅读


重要特征

整体二分是一种基于值域的整体分治算法

询问的答案具有可二分性
修改对判定答案的贡献互相独立 ,修改之间互不影响效果
修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值
贡献满足交换律,结合律,具有可加性*
题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》

优点:
常数极小,配合树状数组往往可以获得比各类高级数据结构或者套线段树的整体二分优秀很多的复杂度
好写易懂

诸多求第𝑘大 第𝑘小的题目都可以用整体二分来解决
整体二分可以解决的问题都可以用:
归并树、可持久化线段树、各类“树套数”大力数据结构来解决

算法思路

首先整体二分必须是基于时间的
在分治的过程中我们通常要写一个数据结构以支持查询和修改𝑚𝑖𝑑和当前询问or操作之间的关系
假设当前二分到的答案为mid,根据每一次操作与mid之间的关系我们把操作分为𝑙𝑒𝑓𝑡操作序列和𝑟𝑖𝑔ℎ𝑡操作序列
当$𝑙𝑒𝑓𝑡{𝑣𝑎𝑙} = 𝑟𝑖𝑔ℎ𝑡{𝑣𝑎𝑙}$ 时,记录答案,返回

例题

K-th number

考虑依据值域二分
假设当前二分到的答案为𝑚𝑖𝑑,我们分别讨论修改和查询
假设当先要修改的位置为𝑝𝑜𝑠,修改的值为𝑣𝑎𝑙
分为两种情况:
𝑣𝑎𝑙𝑚𝑖𝑑 说明val更改以后会对答案造成影响,那么更新这一段的值,并且此操作还可能会对下一次分治的答案有影响,加入左询问序列。
val>𝑚𝑖𝑑 此时修改的值已经比我们二分的答案还大了,必然不会是第𝑘小的数,加入右询问序列,不更新。

对于询问操作,我们先查询此询问的区间内有多少个≤𝑚𝑖𝑑的数,记作tot,分情况讨论
$𝑘𝑖≤𝑡𝑜𝑡答案仍在[𝑟𝑎𝑛𝑔𝑒{𝑙𝑒𝑓𝑡}, 𝑚𝑖𝑑]中,加入左询问序列𝑘𝑖>𝑡𝑜𝑡答案在[𝑚𝑖𝑑+1,𝑟𝑎𝑛𝑔𝑒{𝑟𝑖𝑔ℎ𝑡}]中,等价于在[𝑚𝑖𝑑+1,𝑟𝑎𝑛𝑔𝑒{𝑟𝑖𝑔ℎ𝑡}]值域中,查找𝑘{𝑖−𝑡𝑜𝑡}大的数,将𝑘_{𝑖−𝑡𝑜𝑡}后加入右询问序列
这样的操作使得左右两个询问序列各构成子问题,值域上或下届减小,询问数量减小,以保证
O(𝑁𝑙𝑜𝑔𝑆𝐼𝑍𝐸)(其中𝑆𝐼𝑍𝐸$为值域大小)的复杂度

Tips:
每次操作过后记得还原树状数组
按照时间顺序还原原询问序列

核心代码:

inline void solve(int lval, int rval, int st, int ed)
{
    if (st > ed) return;
    if (lval == rval) {
        for (int i = st; i <= ed; ++ i) {
            if (q[i].opt > 0) ans[q[i].opt] = lval;
        }
        return;
    }
    int mid = (lval + rval) >> 1;
    int ltot = 0, rtot = 0;
    for (int i = st; i <= ed; ++ i) {
        if (q[i].opt == 0) {
            if (q[i].r <= mid) modify(q[i].l, 1), lq[++ ltot] = q[i];
            else rq[++ rtot] = q[i];
        }
        else {
            int tot = query(q[i].r) - query(q[i].l - 1);
            if (tot >= q[i].val) lq[++ ltot] = q[i];
            else q[i].val -= tot, rq[++ rtot] = q[i];
        }
    }
    for (int i = ed; i >= st; -- i) {
        if (q[i].opt == 0 && q[i].r <= mid) modify(q[i].l, -1);
    }
    for (int i = 1; i <= ltot; ++ i) q[st + i - 1] = lq[i];
    for (int i = 1; i <= rtot; ++ i) q[st + ltot + i - 1] = rq[i];
    solve(lval, mid, st, st + ltot - 1);
    solve(mid + 1, rval, st + ltot, ed);
}


朴实沉毅