整體二分

本來感覺挺神秘的一個東西， 學完了似乎沒有多難， 放幾個板子隨便寫寫吧（今天數學不想做題）

從最最最最人盡皆知的區間第 \(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;
}