zcmimi's blog

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,LG P3834 【模板】可持久化线段树 1(主席树)

如果l=r,直接[st,ed]答案都是l

和普通二分一样,设m=\frac {l+r}2

如果 是原序列中的数 且 大于m , 在树状数组中对应位置+1

如果是询问操作,设x为树状数组中询问区间的总和,

x \ge k则分配到左区间,

否则分配到右区间,k=k-x.

具体看代码:

#include<bits/stdc++.h>
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=200011;
int n,q,ans[N],s[N];
inline void add(int x,int v){for(;x<=n;x+=x&-x)s[x]+=v;}
inline int ask(int x){int res=0;for(;x;x-=x&-x)res+=s[x];return res;}
struct que{int typ,id,l,r,k;}a[N<<1],a1[N<<1],a2[N<<1];
void solve(int l,int r,int st,int ed){
    if(st>ed||l>r)return;
    if(l==r){for(int i=st;i<=ed;++i)ans[a[i].id]=l;return;}
    int m=(l+r)>>1,c1=0,c2=0;
    for(int i=st;i<=ed;++i)
    if(a[i].typ){
        if(a[i].k<=m)add(a[i].l,1),a1[++c1]=a[i];
        else a2[++c2]=a[i];
    }
    else{
        int x=ask(a[i].r)-ask(a[i].l-1);
        if(a[i].k<=x)a1[++c1]=a[i];
        else a[i].k-=x,a2[++c2]=a[i];
    }
    // 可以清空树状数组,也可以直接将加上的减去,后者更快
    for(int i=1;i<=c1;++i)if(a1[i].typ)add(a1[i].l,-1);
    for(int i=1;i<=c1;++i)a[st+i-1]=a1[i];
    for(int i=1;i<=c2;++i)a[st+c1+i-1]=a2[i];
    solve(l,m,st,st+c1-1);
    solve(m+1,r,st+c1,ed);
}
int main(){
    in(n,q);
    int x,l,r,k;
    for(int i=1;i<=n;++i)in(x),a[i]={1,0,i,0,x};
    for(int i=1;i<=q;++i)in(l,r,k),a[n+i]={0,i,l,r,k};
    solve(-1e9,1e9,1,n+q);
    for(int i=1;i<=q;++i)out(ans[i],ln);
    flush();
}
整体二分
comment评论
Search
search