整體二分淺談
整體二分淺談
一、前置知識
在學習整體二分之前，要學會二分，以及二分的分治思想。
二、整體二分淺談及例題
例題： bzoj2527: [Poi2011]Meteors
對於這道題是整體二分的經典例題，我們先拋開整體二分，思考二分怎麼做。對於一個詢問，因為答案有單調性，如果$x$時刻為最小可以時刻，則比$x$小的時刻都不可以，比$x$大的時刻都可以，所以我們可以進行二分答案，並加以驗證。先不說怎樣驗證，就單是時間複雜度就不能接受，$O(nmlog_2^n)$。
如果一個一個進行二分時間複雜度不允許，且這些詢問不是強制線上的，我們不妨整體進行二分，我們把所有詢問放在一起進行二分。我們設計一個函式$solve(l，r，x，y)$，表示當前詢問序列$[x，y]$的答案在當前答案$[l，r]$區間。有一個問題，就是為什麼答案在答案區間$[l，r]$的所有詢問會連線在一起，在詢問序列的連續一段呢？這個問題放在後面，先置之不理。我們思考，怎樣進行二分。
二分答案的思想是取出當前答案區間的中間值進行驗證，如果比答案小，則讓答案的區間的左端點為中間值加一，反之讓答案的右端點為中間值。按照二分答案的思想，我們也進行中間值驗證。看例題，我們思考怎麼驗證。
對於當前答案區間$[l，r]$，我們把第$[l，mid]$場流星雨全部落下，看在當前答案區間$[l，r]$所屬的所有詢問是否在第$[l，mid]$場流星雨下過之後已經收集足夠的隕石，如果當前詢問已經收集夠，我們把它歸為答案區間$[l，mid ]$中，反之我們把它歸為答案區間$[mid+1，r]$中，並且對於歸為答案區間$[mid+1，r]$的詢問我們需要進行修改，對於其希望要收集的隕石數要減去$[l，mid]$場流星雨的隕石總數，此處理解一下。
現在解決一下上面留下的問題，我們怎麼能將答案都在$[x，y]$區間的所有詢問都放在一起呢？我們對於每一次劃分，都將這些詢問進行拷貝，並且修改，然後重新按左右排布，這樣我們就能讓這些答案在同一區間的詢問在一起了。
我們分析一下時間複雜度：我們運用線段樹的思想進行分析，我們一共有$log_2^{r-l+1}$層，在這個式子中的$r$表示答案可能到達的最大值，反之$l$表示的就是答案可能到達的最小值，在本題中，我們的$r=n，l=1$，但是下方的程式碼最開始的傳參為$r=n+1$，這表示前$n$場流星雨都不能滿足這個詢問，所以最後落在$n+1$的所有詢問表示不能在所有$n$個流行雨中的到滿足，故輸出$-1$。每一層中我們運用線段樹的思想，知道遍歷每一層的所有流星雨，一共是線性的時間複雜度，並且每一層正正好好攤分所有$m$個詢問，在每一層中我們每一個詢問和流星雨都會運用樹狀陣列，所以總的時間複雜度是$O((n+m)log_2^{n}log_2^{r-l+1})$。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
struct Per {int head,id;long long need;}per[N],per_[N<<1];
int n,m,k,L[N],R[N];long long A[N];int ans[N],nxt[N],to[N],idx;long long tmp[N<<1];
void add(int a,int b) {nxt[++idx]=per[a].head,to[idx]=b,per[a].head=idx;}
void change(int x,long long y) {while(x<=2*m) tmp[x]+=y,x+=x&-x;}
long long find(int x) {long long sum=0;while(x) sum+=tmp[x],x-=x&-x;return sum;}
void solve(int l,int r,int x,int y)
{
if(l==r) {for(int i=x;i<=y;i++) ans[per[i].id]=l;return;}
int mid=(l+r)>>1,tl=0,tr=n;
for(int i=l;i<=mid;i++) change(L[i],A[i]),change(R[i]+1,-A[i]);
for(int i=x;i<=y;i++)
{
long long tmp1=0;
for(int j=per[i].head;j&&tmp1<=per[i].need;j=nxt[j])
tmp1+=find(to[j]+m)+find(to[j]);
if(tmp1>=per[i].need) per_[++tl]=per[i];
else per_[++tr]=per[i],per_[tr].need-=tmp1;
}
for(int i=l;i<=mid;i++) change(L[i],-A[i]),change(R[i]+1,A[i]);
for(int i=1;i<=tl;i++) per[x+i-1]=per_[i];
for(int i=n+1;i<=tr;i++) per[x+tl+i-n-1]=per_[i];
solve(l,mid,x,x+tl-1),solve(mid+1,r,y-tr+n+1,y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,a;i<=m;i++) scanf("%d",&a),add(a,i);
for(int i=1;i<=n;i++) scanf("%lld",&per[i].need),per[i].id=i;
scanf("%d",&k);for(int i=1;i<=k;i++) scanf("%d%d%lld",&L[i],&R[i],&A[i]);
for(int i=1;i<=k;i++) if(R[i]<L[i]) R[i]+=m; solve(1,k+1,1,n);
for(int i=1;i<=n;i++) (ans[i]==k+1)?printf("NIE\n"):printf("%d\n",ans[i]);
}
三、習題
題解：這道題我們可以運用主席樹，或是樹狀陣列來解決。但是我們這道題要運用整體二分來解決，我們發現這道和上一道題差不多，也是區間覆蓋，但是是找第$k$大的，同樣與上一道題一樣，我們每一次進行驗證答案的中間值，並進行左右遞迴，最後處理出答案。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
#define mod 19921228
int n,num[N],placel[N],placer[N],number[N],ans[N],idx,tmp[N],P[N],C[N],L[N],R[N];
struct Doll {int id,p,l,r,k,val;}doll[N],doll_[N];
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0,f=1; char c=nc(); while(c<48)
{if(c=='-') f=-1;c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
bool cmp(const Doll &a,const Doll &b) {return a.val>b.val;}
void change(int x,int y) {while(x<=idx) tmp[x]+=y,x+=x&-x;}
int find(int x) {int sum=0;while(x) sum+=tmp[x],x-=x&-x;return sum;}
int find_ord(int x) {int l=1,r=idx+1;
while(l<r) {int mid=(l+r)>>1;(number[mid]>=x)?r=mid:l=mid+1;}return l;}
void solve(int l,int r,int x,int y)
{
if(l==r) {for(int i=x;i<=y;i++) ans[doll[i].id]=num[l];return;}
int mid=(l+r)>>1,tl=0,tr=n;
for(int i=l;i<=mid;i++) change(placel[i],1),change(placer[i]+1,-1);
for(int i=x;i<=y;i++)
{
int tmp1=find(doll[i].p);
if(tmp1>=doll[i].k) doll_[++tl]=doll[i];
else doll_[++tr]=doll[i],doll_[tr].k-=tmp1;
}
for(int i=l;i<=mid;i++) change(placel[i],-1),change(placer[i]+1,1);
for(int i=1;i<=tl;i++) doll[x+i-1]=doll_[i];
for(int i=n+1;i<=tr;i++) doll[x+tl+i-n-1]=doll_[i];
solve(l,mid,x,x+tl-1),solve(mid+1,r,y-tr+n+1,y);
}
int main()
{
n=rd();
int Padd=rd(),Pfirst=rd(),Pmod=rd(),Pprod=rd();
int Cadd=rd(),Cfirst=rd(),Cmod=rd(),Cprod=rd();
int Ladd=rd(),Lfirst=rd(),Lmod=rd(),Lprod=rd();
int Radd=rd(),Rfirst=rd(),Rmod=rd(),Rprod=rd();
P[1]=Pfirst%Pmod; for(int i=2;i<=n;i++) P[i]=(1ll*P[i-1]*Pprod+Padd+i)%Pmod;
C[1]=Cfirst%Cmod; for(int i=2;i<=n;i++) C[i]=(1ll*C[i-1]*Cprod+Cadd+i)%Cmod;
L[1]=Lfirst%Lmod; for(int i=2;i<=n;i++) L[i]=(1ll*L[i-1]*Lprod+Ladd+i)%Lmod;
R[1]=Rfirst%Rmod; for(int i=2;i<=n;i++) R[i]=(1ll*R[i-1]*Rprod+Radd+i)%Rmod;
for(int i=1;i<=n;i++) if(L[i]>R[i]) swap(L[i],R[i]);
for(int i=1;i<=n;i++) doll[i].l=L[i],doll[i].r=R[i],
doll[i].p=P[i],doll[i].val=C[i],doll[i].k=i,doll[i].id=i;
for(int i=1;i<=n;i++) number[++idx]=doll[i].p,number[++idx]=doll[i].l,number[++idx]=doll[i].r;
sort(number+1,number+idx+1);
for(int i=1;i<=n;i++)
doll[i].p=find_ord(doll[i].p),doll[i].l=find_ord(doll[i].l),doll[i].r=find_ord(doll[i].r);
sort(doll+1,doll+n+1,cmp);
for(int i=1;i<=n;i++) num[i]=doll[i].val,doll[i].val=i,placel[i]=doll[i].l,placer[i]=doll[i].r;
solve(1,n+1,1,n); for(int i=1;i<=n;i++) (ans[i]+=ans[i-1])%=mod; printf("%d\n",ans[n]);
}