【學習筆記】整體二分
一、簡述
叫簡述是因為不知道該叫啥。
整體二分是一種基于值域的分治算法，一般面對多次可二分的詢問時就可以整體二分。有時帶修改的問題也可以整體二分，但顯然它難以強制在線。
整體二分的精髓在于對于一堆問題只 check 一次，從而節省相當多的時間。
二、例題
1.Luogu P3834 【模板】可持久化線段樹 2
考慮如何高效地確定一些詢問的答案與當前 \(mid\) 的關系。
考慮樹狀數組，將 \([l,mid]\) 中的數全都插入到對應的位置上。于是對于每個詢問，就可以用樹狀數組來求出詢問區間中 \([l,mid]\) 的數量。于是就好做了。時間復雜度 \(O(n\log^2n)\)，需要離散化。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
//int cnt;
int n,m,a[maxn],lsh[maxn],tot,ans[maxn];
struct{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
}F;
struct node1{
int p,v;
node1(int p=0,int v=0):p(p),v(v){}
};
struct node2{
int l,r,k,id;
node2(int l=0,int r=0,int k=0,int id=0):l(l),r(r),k(k),id(id){}
};
il void solve(int l,int r,vector<node1> p,vector<node2> q){
// cerr<<l<<" "<<r<<" "<<p.size()<<" "<<q.size()<<"\n";
if(l==r){
for(node2 i:q){
ans[i.id]=lsh[l];
}
return ;
}
int mid=(l+r)>>1;
vector<node1> p1,p2;
for(node1 i:p){
if(i.v<=mid){
F.add(i.p,1);
p1.pb(i);
}
else{
p2.pb(i);
}
}
vector<node2> q1,q2;
for(node2 &i:q){
// cnt++;
int tmp=F.query(i.r)-F.query(i.l-1);
if(i.k<=tmp){
q1.pb(i);
// cerr<<"1 ";
}
else{
i.k-=tmp;
q2.pb(i);
}
}
// cerr<<"\n"<<q1.size()<<"\n";
for(node1 i:p){
if(i.v<=mid){
F.add(i.p,-1);
}
}
solve(l,mid,p1,q1);
solve(mid+1,r,p2,q2);
}
int main(){
// freopen("P3834_6.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
lsh[++tot]=a[i];
}
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
vector<node1> p;
for(int i=1;i<=n;i++){
a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
p.pb(node1(i,a[i]));
}
vector<node2> q;
for(int i=1,l,r,k;i<=m;i++){
cin>>l>>r>>k;
q.pb(node2(l,r,k,i));
}
solve(1,tot,p,q);
// cerr<<cnt<<"\n";
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
2.[bzoj1901][Zju2112] Dynamic Rankings
首先可以將更改操作改為一個刪除操作再加一個插入操作。將所有的操作和查詢存在一個操作序列中進行分治。對于當前的 \(mid\)，如果一個修改操作要修改的數大于 \(mid\)，那么它對左區間就不會有影響，直接放入右區間。否則就將貢獻加入樹狀數組，放入左區間即可。注意維持操作序列的時間順序。
實際上是可以不離散化的，對時間復雜度的影響不大，但要注意必須特判掉空的操作序列區間，否則就會跑滿整個 dfs 樹，這樣的時間復雜度是無法承受的。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,a[maxn],cnt,ans[maxn];
struct node{
int typ,l,k,r,id;
node(int typ=0,int l=0,int k=0,int r=0,int id=0)
:typ(typ),l(l),k(k),r(r),id(id){}
}b[maxn*3],hp[maxn*3];
struct{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
}F;
il void solve(int l,int r,int L,int R){
if(l>r){
return ;
}
// if(l!=10||r!=9){
// cout<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
// }
if(L==R){
for(int i=l;i<=r;i++){
ans[b[i].id]=L;
}
return ;
}
int pl=l,pr=r;
int mid=(L+R)>>1;
for(int i=l;i<=r;i++){
if(b[i].typ){
if(b[i].k<=mid){
F.add(b[i].l,b[i].typ);
hp[pl++]=b[i];
}
else{
hp[pr--]=b[i];
}
}
else{
int tmp=F.query(b[i].r)-F.query(b[i].l-1);
if(tmp>=b[i].k){
hp[pl++]=b[i];
}
else{
b[i].k-=tmp;
hp[pr--]=b[i];
}
}
}
for(int i=l;i<=r;i++){
if(b[i].typ&&b[i].k<=mid){
F.add(b[i].l,-b[i].typ);
}
}
for(int i=l;i<pl;i++){
b[i]=hp[i];
}
for(int i=pl,j=r;i<=r;i++,j--){
b[i]=hp[j];
}
solve(l,pr,L,mid);
solve(pl,r,mid+1,R);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[++cnt]=node(1,i,a[i]);
}
for(int i=1;i<=m;i++){
char typ;
cin>>typ;
if(typ=='Q'){
int l,r,k;
cin>>l>>r>>k;
b[++cnt]=node(0,l,k,r,i);
}
else{
int p,v;
cin>>p>>v;
b[++cnt]=node(-1,p,a[p]);
b[++cnt]=node(1,p,v);
a[p]=v;
ans[i]=-1;
}
}
solve(1,cnt,0,1e9);
for(int i=1;i<=m;i++){
if(~ans[i]){
cout<<ans[i]<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
3.[國家集訓隊] 矩陣乘法
依然是區間第 \(k\) 大，只不過改成了矩陣，使用二維樹狀數組即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
}
using IO::read;
const int maxn=6e4+5,maxm=3.2e5+5;
int n,m,cnt,a[505][505],ans[maxn];
struct{
int tr[505][505];
il int lowbit(int x){
return x&-x;
}
il 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)){
tr[i][j]+=v;
}
}
}
il 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+=tr[i][j];
}
}
return res;
}
}F;
struct node{
int x1,y1,k,x2,y2,id;
node(int x1=0,int y1=0,int k=0,int x2=0,int y2=0,int id=0)
:x1(x1),y1(y1),x2(x2),y2(y2),k(k),id(id){}
}b[maxm],hp[maxm];
il void solve(int l,int r,int L,int R){
if(l>r){
return ;
}
if(L==R){
for(int i=l;i<=r;i++){
ans[b[i].id]=L;
}
return ;
}
int mid=(L+R)>>1,pl=l,pr=r;
for(int i=l;i<=r;i++){
if(b[i].id){
int x1=b[i].x1,y1=b[i].y1,x2=b[i].x2,y2=b[i].y2;
int tmp=F.query(x2,y2)-F.query(x1-1,y2)-F.query(x2,y1-1)+F.query(x1-1,y1-1);
if(tmp>=b[i].k){
hp[pl++]=b[i];
}
else{
b[i].k-=tmp;
hp[pr--]=b[i];
}
}
else{
if(b[i].k<=mid){
F.add(b[i].x1,b[i].y1,1);
hp[pl++]=b[i];
}
else{
hp[pr--]=b[i];
}
}
}
for(int i=l;i<=r;i++){
if(!b[i].id&&b[i].k<=mid){
F.add(b[i].x1,b[i].y1,-1);
}
}
for(int i=l;i<pl;i++){
b[i]=hp[i];
}
for(int i=pl,j=r;i<=r;i++,j--){
b[i]=hp[j];
}
solve(l,pr,L,mid);
solve(pl,r,mid+1,R);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=read();
b[++cnt]=node(i,j,a[i][j]);
}
}
for(int i=1,x1,y1,x2,y2,k;i<=m;i++){
x1=read(),y1=read(),x2=read(),y2=read(),k=read();
b[++cnt]=node(x1,y1,k,x2,y2,i);
}
solve(1,cnt,0,1e9);
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
4.[THUPC2017] 天天愛射擊
整體二分，將每個木板被擊碎的時間二分出來即可。注意有的木板可能根本無法擊穿。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,a[maxn],ans[maxn];
struct node{
int x1,x2,k;
}b[maxn],hp[maxn];
struct{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=2e5;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
}F;
il void solve(int l,int r,int L,int R){
if(l>r){
return ;
}
if(L==R){
for(int i=l;i<=r;i++){
if(b[i].x1<=a[L]&&b[i].x2>=a[L]&&b[i].k==1){
ans[L]++;
}
}
return ;
}
int mid=(L+R)>>1,pl=l,pr=r;
for(int i=L;i<=mid;i++){
F.add(a[i],1);
}
for(int i=l;i<=r;i++){
int tmp=F.query(b[i].x2)-F.query(b[i].x1-1);
if(tmp>=b[i].k){
hp[pl++]=b[i];
}
else{
b[i].k-=tmp;
hp[pr--]=b[i];
}
}
for(int i=L;i<=mid;i++){
F.add(a[i],-1);
}
for(int i=l;i<pl;i++){
b[i]=hp[i];
}
for(int i=pl,j=r;i<=r;i++,j--){
b[i]=hp[j];
}
solve(l,pr,L,mid);
solve(pl,r,mid+1,R);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>b[i].x1>>b[i].x2>>b[i].k;
}
for(int i=1;i<=m;i++){
cin>>a[i];
}
solve(1,n,1,m);
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
5.「CTSC2018」混合果汁
考慮對于單次詢問，顯然可以二分，每次將美味度大于等于 \(mid\) 的果汁放在一起按價格排序，貪心地計算能否在 \(g_j\) 的限制內買夠 \(L_j\) 的果汁。
多次詢問可二分的問題，這提醒我們去做整體二分。但是有一個問題，我們無法在整體二分搜索樹上的每個節點都對大于等于 \(mid\) 的果汁進行排序計算，不然顯然會炸。有一個解決方案是，將一堆沒有交集的搜索樹節點放在一起計算，用線段樹維護按美味度排序后的某個后綴果汁集合。具體地，按照美味度倒著掃，對于每個美味度在 \([L,R]\) 的搜索樹節點，我們先將 \([mid+1,R]\) 的果汁加入線段樹，然后處理節點上的詢問，再將 \([L,mid]\) 的果汁加入線段樹。換言之，我們要按層遍歷搜索樹，并且每一層還要倒著遍歷！一個方案是用 std::vector 存儲當前層的搜索樹節點寫 bfs。時間復雜度 \(O((n+m)\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,lsh[maxn];
ll ans[maxn];
struct jui{
int d,p,l;
}a[maxn];
struct{
int id;
ll g,l;
}b[maxn],hp[maxn];
int rt,tot;
struct{
int ls,rs,d,p,l;
ll smp,sml;
}tr[maxn<<1];
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define d(id) tr[id].d
#define p(id) tr[id].p
#define l(id) tr[id].l
#define smp(id) tr[id].smp
#define sml(id) tr[id].sml
il void pushup(int id){
smp(id)=smp(ls(id))+smp(rs(id));
sml(id)=sml(ls(id))+sml(rs(id));
}
il void insert(int &id,int L,int R,int p,int d,int l){
if(!id){
id=++tot;
ls(id)=rs(id)=0;
d(id)=p(id)=l(id)=0;
smp(id)=sml(id)=0;
}
if(L==R){
smp(id)=lsh[p]*1ll*l;
sml(id)=l;
d(id)=d,p(id)=lsh[p],l(id)=l;
return ;
}
int mid=(L+R)>>1;
if(p<=mid){
insert(ls(id),L,mid,p,d,l);
}
else{
insert(rs(id),mid+1,R,p,d,l);
}
pushup(id);
}
il ll query(int id,int L,int R,ll g){
if(!id){
return 0;
}
if(L==R){
return min(g/p(id),l(id)*1ll);
}
int mid=(L+R)>>1;
if(smp(ls(id))>=g){
return query(ls(id),L,mid,g);
}
else{
return query(rs(id),mid+1,R,g-smp(ls(id)))+sml(ls(id));
}
}
#undef ls
#undef rs
#undef d
#undef p
#undef l
#undef smp
#undef sml
struct node{
int L,R,l,r;
node(int L=0,int R=0,int l=0,int r=0):L(L),R(R),l(l),r(r){}
};
vector<node> q[2];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].d>>a[i].p>>a[i].l;
}
sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.p<y.p;});
for(int i=1;i<=n;i++){
lsh[i]=a[i].p;
a[i].p=i;
}
sort(a+1,a+n+1,[](const jui &x,const jui &y){return x.d>y.d;});
for(int i=1;i<=m;i++){
cin>>b[i].g>>b[i].l;
b[i].id=i;
}
q[0].pb(node(1,1e5,1,m));
int cur=0;
while(q[cur].size()){
q[cur^1].clear();
int now=1;
rt=tot=0;
for(node x:q[cur]){
int L=x.L,R=x.R,l=x.l,r=x.r;
// cout<<L<<" "<<R<<":\n";
// for(int i=l;i<=r;i++){
// cout<<b[i].id<<" ";
// }
// puts("");
if(l>r){
continue;
}
if(L==R){
while(now<=n&&a[now].d>=L){
insert(rt,1,n,a[now].p,a[now].d,a[now].l);
now++;
}
for(int i=l;i<=r;i++){
if(query(rt,1,n,b[i].g)>=b[i].l){
ans[b[i].id]=L;
}
else{
ans[b[i].id]=-1;
}
}
continue;
}
int mid=(L+R)>>1;
while(now<=n&&a[now].d>mid){
insert(rt,1,n,a[now].p,a[now].d,a[now].l);
now++;
}
int pl=l,pr=r;
for(int i=l;i<=r;i++){
if(query(rt,1,n,b[i].g)>=b[i].l){
hp[pr--]=b[i];
}
else{
hp[pl++]=b[i];
}
}
for(int i=l;i<pl;i++){
b[i]=hp[i];
}
for(int i=pl;i<=r;i++){
b[i]=hp[i];
}
q[cur^1].pb(node(mid+1,R,pl,r));
q[cur^1].pb(node(L,mid,l,pr));
while(now<=n&&a[now].d>=L){
insert(rt,1,n,a[now].p,a[now].d,a[now].l);
now++;
}
}
cur^=1;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號