整体二分

本来感觉挺神秘的一个东西，学完了似乎没有多难，放几个板子随便写写吧（今天数学不想做题）

从最最最最人尽皆知的区间第 k 大问题开始吧

引入

如果我想问你一个序列中的区间的第 k 大，你会如何？

显然我们直接二分就行（主席树学傻的滚）

时间复杂度为 O(nlogn) 感觉挺不错的呢

但是如果我们有一大堆询问，我们的时间复杂度就会直接被干到 O(qnlogn) ，这个东西都没我快，我们肯定是很不满意的

这时候就要引出我们的整体二分了

与其说是二分，其实我觉得更像是分治，利用可二分问题的性质

比如说我们想要解决这个经典区间第 k 大的问题

我们使用一个容器存储当前 [l，r] 的加点，询问信息

注意这里的 [l,r] 和如果只有一个操作一样，指的是值而非位置，平常二分是什么这个 l,r 就是什么

我这里就使用一个存结构体的 vector 了

结构体里边有 x,y,k,id,type

其中 type 代表的是所记录的操作是属于添加还是删除，根据我的习惯，我们就使用 0 代表这个操作是添加， 1 代表这个操作是询问

在 type=1 中， x,y,k,id 分别代表的是询问左端点，右端点，求第 k 大，询问编号(输出用，我们搞得离线)

在 type=0 中， x,id 分别代表当前位置的值和当前位置编号，其他位置没有意义

这两个的存贮是不干扰的，为什么最好放到一个里我们之后再说，我们把所有添加放到最前面

之后我们开始我们的算法：

当前我们处理到区间 [l,r] 了，有一个容器 tmp 记录着作用于当前区间的操作

如果 l=r，即为当前已经锁定了一个值，我们就将容器中所有的询问直接设为 l 就行，注意按照 id 存储，直接返回即可，反之向下继续走

我们找出来 mid，开两个容器表示我们向下 [l,mid] 和 [mid+1,r] 的容器，方便我们向下分治使用，还需要一个数据结构维护我们需要的信息

在这个问题中，我们决定一个询问是向 [l,mid] 还是 [mid+1,r] 是取决于比当前询问 k 大的数字有几个的，我们使用树状数组就可以维护，我们首先处理添加操作

我们将值在当前 mid 左边的添加操作加上去，对应的，也就是在树状数组对应位置处加上 1 （是 id 哦）

过程中我们将值小于等于 mid 的放到 [l,mid] 的容器中，反之同理

之后我们 mid 往左的都处理好了，之后对于排在后边的若干个询问，我们只需要查询在 [x,y] 之间有多少个

如果比当前 k 大，这个询问放到 [l,mid] ,反之同理

最后别忘了我们这个树状数组只为了我们确定询问下放的位置，对不同 mid 也不同，我们需要清空树状数组

递归下去就行

我们放一下代码罢

代码如下↓

cpp
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6;
struct Node{int x, y, k, id, type;};
struct BIT{
    int tr[MN], n;
    void init(int num){
        n=num; memset(tr,0,sizeof(tr));}
    int lowbit(int x){
        return x&(-x);}
    void update(int pos, int val){
        for(int i=pos; i<=n; i+=lowbit(i)) tr[i]+=val;}
    int qval(int pos){
        int res=0; for(int i=pos; i; i-=lowbit(i)) res+=tr[i];
        return res;}
    int query(int l, int r){
        return qval(r)-qval(l-1);}
}bit;
int n, q, ans[MN];
void solve(vector <Node> tmp, int l, int r){
    if(tmp.empty()) return;
    if(l==r){
        for(int j=0; j<tmp.size(); ++j)
            if(tmp[j].type)
                ans[tmp[j].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    vector <Node> tmp1, tmp2;
    for(int j=0; j<tmp.size(); ++j){
        if(!tmp[j].type){
            if(tmp[j].x<=mid){
                bit.update(tmp[j].id,1);
                tmp1.push_back(tmp[j]);
            }else{
                tmp2.push_back(tmp[j]);
            }
        }else{
            int res=bit.query(tmp[j].x,tmp[j].y);
            if(res>=tmp[j].k){
                tmp1.push_back(tmp[j]);
            }else{
                tmp[j].k-=res;
                tmp2.push_back(tmp[j]);
            }
        }
    }
    for(int j=0; j<tmp1.size(); ++j) if(!tmp1[j].type) bit.update(tmp1[j].id,-1);
    solve(tmp1,l,mid); solve(tmp2,mid+1,r);
}
vector <Node> tot;
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>q; bit.init(n+1);
    for(int i=1; i<=n; ++i){
        int val; cin>>val;
        tot.push_back({val,0,0,i,0});
    }
    for(int i=1; i<=q; ++i){
        int l, r, k; cin>>l>>r>>k;
        tot.push_back({l,r,k,i,1});
    }
    solve(tot,0,0x3f3f3f3f);
    for(int i=1; i<=q; ++i) cout<<ans[i]<<'\n';
    return 0;
}

有点小压行，不影响

我们看一下带修改的怎么写（树套树狗都不写）

就这个，唯一的区别是加了一个修改操做，我们加一个 type 表示修改

同理做就好

#include <bits/stdc++.h>
using namespace std;
const int MN=5e5+515;

struct BIT{
    int tr[MN],n;
    int lowbit(int x){return x&-x;}
    void update(int x,int v){
        for(;x<=n;x+=lowbit(x)) tr[x]+=v;
    }
    int query(int x){
        int res=0;for(;x;x-=lowbit(x)) res+=tr[x];
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
}bit;

struct Node{int x,y,k,id,type;};
int n,q,ans[MN],a[MN];
char op[MN];
vector<Node> qry;

void solve(vector<Node> q,int l,int r){
    if(q.empty()) return;
    if(l==r){
        for(auto i:q) if(i.type==2) ans[i.id]=l;
        return;
    }
    int mid=(l+r)>>1;
    vector<Node> q1,q2;
    vector<pair<int,int>> hs;
    for(auto i:q){
        if(!i.type){
            if(i.x<=mid){
                bit.update(i.id,1);
                hs.emplace_back(i.id,1);
                q1.push_back(i);
            }else q2.push_back(i);
        }else if(i.type==1){
            if(i.y<=mid){
                bit.update(i.x,-1);
                hs.emplace_back(i.x,-1);
                q1.push_back(i);
            }else q2.push_back(i);
        }else{
            int res=bit.query(i.x,i.y);
            if(res>=i.k) q1.push_back(i);
            else i.k-=res,q2.push_back(i);
        }
    }
    for(auto [x,y]:hs) bit.update(x,-y);
    solve(q1,l,mid);solve(q2,mid+1,r);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q; bit.n=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        qry.push_back({a[i],0,0,i,0});
    }
    for(int i=1;i<=q;i++){
        cin>>op[i];
        if(op[i]=='C'){
            int x,y;cin>>x>>y;
            qry.push_back({x,a[x],0,0,1});
            qry.push_back({y,0,0,x,0});
            a[x]=y;
        }else{
            int l,r,k;cin>>l>>r>>k;
            qry.push_back({l,r,k,i,2});
        }
    }
    solve(qry,0,1e9);
    for(int i=1;i<=q;i++) if(op[i]=='Q') cout<<ans[i]<<'\n';
    return 0;
}

再放一个吧......

这个大概说一下吧

题意就是我们有一个环（不会有我这样的弱智没有读出来吧），每个点属于一个国家，有一些操作，从 l 开始顺时针走一直到 r ，其中每一个点加上 v ，每一个国家有一个值，询问每个国家至少到什么时候才凑齐这个值

我们对于时间二分，使用差分+树状数组维护一下就行了

代码↓

#include <bits/stdc++.h>
using namespace std;
const int MN=3e5+315;
struct Add_Node{int l, r; long long val; int id;};
struct Query_Node{int id, val;};
int n, m;
long long ans[MN];
vector <int> sta[MN];
struct Bit{
    long long tr[MN];
    int lowbit(int x){
        return x&(-x);}
    void update(int pos, long long val){
        for(int i=pos; i<=m; i+=lowbit(i)) tr[i]+=val;}
    void update_range(int l, int r, long long val){
        update(l,val); update(r+1,-val);}
    int qval(long long pos){
        int res=0; for(int i=pos; i; i-=lowbit(i)) res+=tr[i];
        return res;}
}bit;
long long query(int x, int p){
    long long res=0;
    for(auto v:sta[x]){
        res+=bit.qval(v);
        if(res>=p) return -1;
    }
    return res;
}
void solve(vector <Add_Node> addtmp, vector <Query_Node> querytmp, int l, int r){
    if(l==r){
        for(auto v:querytmp) ans[v.id]=l;
        return;
    }
    int mid=(l+r)>>1;
    vector <Add_Node> addtmp_l, addtmp_r;
    vector <Query_Node> querytmp_l, querytmp_r;
    for(auto v:addtmp){
        if(v.id<=mid){
            if(v.l<=v.r){
                bit.update_range(v.l,v.r,v.val);
            }else{
                bit.update_range(v.l,m,v.val);
                bit.update_range(1,v.r,v.val);
            }
            addtmp_l.push_back(v);
        }else{
            addtmp_r.push_back(v);
        }
    }
    for(auto v:querytmp){
        int res=query(v.id,v.val);
        if(res==-1){
            querytmp_l.push_back(v);
        }else{
            v.val-=res;
            querytmp_r.push_back(v);
        }
    }
    for(auto v:addtmp_l){
        if(v.l<=v.r){
            bit.update_range(v.l,v.r,-v.val);
        }else{
            bit.update_range(v.l,m,-v.val);
            bit.update_range(1,v.r,-v.val);
        }    
    }
    solve(addtmp_l,querytmp_l,l,mid);
    solve(addtmp_r,querytmp_r,mid+1,r);
}
vector <Add_Node> addtot;
vector <Query_Node> querytot;
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1,val; i<=m; ++i){
        cin>>val; sta[val].push_back(i);
    }
    for(int i=1,val; i<=n; ++i){
        cin>>val; querytot.push_back({i,val});
    }
    int q; cin>>q;
    for(int i=1; i<=q; ++i){
        int l, r, val; cin>>l>>r>>val;
        addtot.push_back({l,r,val,i});
    }
    solve(addtot,querytot,1,q+1);
    for(int i=1; i<=n; ++i){
        if(ans[i]==q+1) cout<<"NIE\n";
        else cout<<ans[i]<<'\n';
    }
    return 0;
}

菜单

分享

引入

评论

数论学习笔记

2025.6.26模拟赛-来点不一样的做法吧

Mr.Tenna's TV Time!

16 ABC404 A ~ E 题解

组合数学学习笔记

Slope Trick 学习笔记

博弈论半家桶——从入门到门入从

（勿入）帮一个大学生通过小测

模拟赛T2 hack

高精度模板