整体二分¶

因为整体二分要比二分的难度高上很多，所以这里另外开一个页面讲整体二分。

整体二分¶

整体二分是一种算法思想，通常用于解决一些特定的数据结构和算法问题。它主要用于处理序列或树形结构中的问题，通过递归地将数据集划分为两个相对等的部分，然后在每一部分独立地进行处理，最后将结果合并起来。

以下是整体二分的基本步骤：

划分：将问题规模较大的数据集划分为两个规模较小的子集。
递归处理：对每个子集递归地应用相同的处理方法。
合并结果：将子集的处理结果合并起来，形成整个数据集的处理结果。整体二分在以下几种情况下特别有用：
离线算法：在无法即时处理查询的问题中，可以先将所有查询离线下来，然后使用整体二分的方法进行处理。
树状数组或线段树：在处理区间问题时，整体二分可以用来减少问题的规模，将大区间问题转化为小区间问题。
可并堆：在处理一些需要动态合并和分裂的数据结构问题时，整体二分可以用来优化合并和分裂的效率。整体二分的一个典型应用是在处理离线区间修改问题时。例如，在一个数组上进行多次区间修改查询操作，整体二分可以用来高效地处理这些操作。在使用整体二分时，通常需要注意以下几点：
确保问题可以递归地划分为两个相对等的部分。
处理子问题时，确保不会影响到其他子问题的解。
合并结果时，确保能够正确地整合子问题的解。

讲解见例题 #2

例题 #1 [国家集训队] 矩阵乘法¶

题目描述

给你一个 $n \times n$ 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 $k$ 小数。

输入格式

第一行有两个整数，分别表示矩阵大小 $n$ 和询问组数 $q$。

第 $2$ 到第 $(n + 1)$ 行，每行 $n$ 个整数，表示这个矩阵。第 $(i + 1)$ 行的第 $j$ 个数表示矩阵第 $i$ 行第 $j$ 列的数 $a_{i, j}$。

接下来 $q$ 行，每行五个整数 $x_1, y_1, x_2, y_2, k$，表示一组询问，要求找到以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩形中的第 $k$ 小数。

数据规模与约定¶

对于 $20\%$ 的数据，保证 $n \leq 100$，$q \leq 10^3$。
对于 $40\%$ 的数据，保证 $n \leq 300$，$q \leq 10^4$。
对于 $60\%$ 的数据，保证 $n \leq 400$，$q \leq 3 \times 10^4$。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 500$，$1 \leq q \leq 6 \times 10^4$，$0 \leq a_{i, j} \leq 10^9$。

思路

看起来好像是使用主席树实现的，但是二维的我们有怎么实现呢？这里可以使用可持久化二维值域线段树吗？

这里我们引入一个新离线算法，叫做**整体二分**。

Code¶

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

const char el='\n';
const bool enable_dbg = 0;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s << ' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

const int N = 3e3 + 5;
const int INF = 1e18;
const int M = 1e6;
const int MOD = 1e9 + 7;

struct node{
    int x,y,u,v;
    int k,id;
}q[M],q1[M],q2[M];

int tot,ans[M];
int n,m,t[N][N];


namespace ctree{

    inline int lowbit(int x){
        return x&-x;
    }

    void add(int x,int y,int v){
        for(int i=x;i<=n;i+=lowbit(i)){
            for(int j=y;j<=n;j+=lowbit(j)){
                t[i][j]+=v;
            }
        }
    }

    int query(int x,int y){
        int res=0;
        for(int i=x;i;i-=lowbit(i)){
            for(int j=y;j;j-=lowbit(j)){
                res+=t[i][j];
            }
        }
        return res;
    }
}using namespace ctree;

void solve(int l,int r,int x,int y){
    dbg(l,r,x,y,el);
    if(l>r)return ;
    if(x==y){//已经走到了一个数字上，且该数对当前区间内的操作都有贡献，那么贡献答案
        for(int i=l;i<=r;i++){
            if(q[i].id)ans[q[i].id]=x;
        }
        return ;
    }

    int len1=0,len2=0,mid=x+y>>1;
    for(int i=l;i<=r;i++){
        if(!q[i].id){
            if(q[i].k<=mid)add(q[i].x,q[i].y,1),q1[++len1]=q[i];
            else q2[++len2]=q[i];
        }else{
            int t=query(q[i].u,q[i].v)-query(q[i].x-1,q[i].v)-query(q[i].u,q[i].y-1)+query(q[i].x-1,q[i].y-1);//二维树状数组，雷雨二维前缀和，提取子矩阵
            if(t>=q[i].k)q1[++len1]=q[i];
            else q[i].k-=t,q2[++len2]=q[i];//更新后丢到右边
        }
    }

    for(int i=1;i<=len1;i++)q[l+i-1]=q1[i];
    for(int i=1;i<=len2;i++)q[l+len1+i-1]=q2[i];//重新分配所有操作
    for(int i=l;i<=l+len1-1;i++){
        if(!q[i].id&&q[i].k<=mid)add(q[i].x,q[i].y,-1);
    }

    solve(l,l+len1-1,x,mid);//注意区间下标
    solve(l+len1,r,mid+1,y);
}

void solve(){
    n=rd,m=rd;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a=rd;
            q[++tot]=(node){i,j,0,0,a,0};
        }
    }
    dbg("ok");
    for(int i=1;i<=m;i++){
        int x=rd,y=rd,a=rd,b=rd,k=rd;
        q[++tot]=(node){x,y,a,b,k,i};
    }

    dbg("ok");
    solve(1,tot,-INF,INF);
    dbg("ok");
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
}

signed main() {
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

例题 #2 [ZJOI2013] K大数查询¶

题目描述

你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。这些集合初始都是空集，有 $m$ 个操作：

1 l r c：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中
2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

输入格式

第一行两个正整数 $n,m$，表示集合个数和操作个数。接下来 $m$ 行，每行四个整数表示一次操作。

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案。

【数据范围】 $1 \le n,m \le 5\times 10^4 $$1\le l,r \le n $$1$ 操作中 $|c|\le n $$2$ 操作中 $1\le c < 2^{63}$

第一眼看到这道题，觉得用平衡树合并，但是发现并不是真的合并，因此时间复杂度爆炸。我们知道集合可以用平衡树来维护，区间查询可以用线段树来写，那么组合一下就是线段树套平衡树的板子了。

但是这里我们不想写什么大数据结构，怎么办呢？

请出我们的整体二分。

既然是二分，那么就需要将查询第K大变成二分答案x后判定≤x的数的个数。

首先构建整体二分的框架：我们在值域上分治

设当前区间为[l,r]，逐个考虑属于当前区间的操作。

如果操作为插入x.v。那么如果x.v>mid，将x插入线段树，并且将这个操作加入右区间。否则加入左区间
如果操作为询问第k大，那么我们考虑当前区间的数的个数s（其实就是右区间的数的个数），如果s>k，那么就说明我们要的数字在右区间，否则在左区间。

注意将x插入线段树指的是在线段树的[x.l,x.r]区间+1。别忘了我们还有一个限制是插入到第[l,r]这些集合内。

在完成一个函数空间内的所有操作后，我们要清空贡献，避免一个数被重复计算。

加入右区间指的是：我们有数字q,ql,qr，分治时传入L,R代表q的[L,R]的询问属于这个区间。加入右区间即把一个q_i加入ql中。在所有询问分组完后，将ql,qr连起来作为新的q，并且设定分界点。

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int

#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}

#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e5;
const int M = 1e7;
const int MOD = 1e9 + 7;


/*
- 思考
- 模拟正确性
- code
- debug
*/

namespace SGT{
    int t[N<<2];
    int tag[N<<2];


    void pushup(int x){
        t[x]=t[x<<1]+t[x<<1|1];
    }
    void addtag(int x,int l,int r,int v){
        tag[x]+=v;
        t[x]+=(r-l+1)*v;
    }

    void pushdown(int x,int l,int r){
        if(!tag[x])return ;
        int mid=l+r>>1;
        addtag(x<<1,l,mid,tag[x]);
        addtag(x<<1|1,mid+1,r,tag[x]);
        tag[x]=0;
    }


    void change(int x,int l,int r,int pl,int pr,int v){
        if(pl>pr)return ;
        if(pl<=l&&pr>=r){
            addtag(x,l,r,v);
            return ;
        }
        pushdown(x,l,r);
        int mid=l+r>>1;
        if(pl<=mid)change(x<<1,l,mid,pl,pr,v);
        if(pr>mid)change(x<<1|1,mid+1,r,pl,pr,v);
        pushup(x);
    }


    int query(int x,int l,int r,int pl,int pr){
//      cdbg(x,l,r,pl,pr);
        if(pl>pr)return 0;
        if(pl<=l&&pr>=r)return t[x];

        pushdown(x,l,r);
        int mid=l+r>>1;
        int res=0;
        if(pl<=mid)res+=query(x<<1,l,mid,pl,pr);
        if(pr>mid)res+=query(x<<1|1,mid+1,r,pl,pr);
        return res;
    }
}using namespace SGT;


struct Query{
    int op,l,r,v,id,qid;
}q[N],lq[N],rq[N];


int ans[N];
int n,m;

void solve(int l,int r,int L,int R){//值域l,r，询问L,R
//  cdbg(l,r,L,R);

    if(l==r){
//      if(q[L].op==2){
//          ans[q[L].qid]=l;
//      }
        for(int i=L;i<=R;i++){
            if(q[i].op==2){
                ans[q[i].qid]=l;
            }
        }
        return ;
    }

    int mid=l+r>>1;
    int cntl=0,cntr=0;
    for(int i=L;i<=R;i++){
        if(q[i].op==1){
            if(q[i].v>mid){
                change(1,1,n,q[i].l,q[i].r,1);
                rq[++cntr]=q[i];
            }else{
                lq[++cntl]=q[i];
            }
        }else{
            int s=query(1,1,n,q[i].l,q[i].r);
            if(s>=q[i].v){ //注意等于号
                rq[++cntr]=q[i];
            }else{
                lq[++cntl]=q[i];
                lq[cntl].v-=s;//记得减去s
            }
        }
    }


    for(int i=L;i<L+cntl;i++){
        q[i]=lq[i-L+1];
    }
    for(int i=L+cntl;i<=R;i++){
        q[i]=rq[i-L-cntl+1];
    }

    for(int i=1;i<=cntr;i++){
        if(rq[i].op==1){
            change(1,1,n,rq[i].l,rq[i].r,-1);
        }
    }




    solve(l,mid,L,L+cntl-1);//注意左右边界！
    solve(mid+1,r,L+cntl,R);    
}

void solve(){   
     n=rd,m=rd;
    int cntq=0;
    for(int i=1;i<=m;i++){
        int op=rd;
        if(op==2)cntq++;
        q[i]={op,rd,rd,rd,i,cntq};
        if(q[i].l>q[i].r)swap(q[i].l,q[i].r);
    }

    solve(-n,n,1,m);

    for(int i=1;i<=cntq;i++){
        cout<<ans[i]<<endl;
    }
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

练习 #1 [ABC348G] Max (Sum - Max)¶

题面翻译

给出 $N$，以及 $A_{1...N},B_{1...N}$。

对于每个 $k\in [1,N]$，找出一个 $1...N$ 的集合 $S$，满足 $|S|=k$ 且 $\sum\limits_{i\in S}A_i-\max\limits_{i\in S}B_i$ 最大，输出这个值。

$1\le N\le 2\times 10^5,\space |A_i|\le 10^9,\space |B_i|\le 2\times 10^{14}$