整体二分入门

电玩女神 2023-08-17 16:00 73阅读 0赞

今天睡到快三点，打印东西到3点半，只是敲了一个整体二分模板

hdu2665  
代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50;
    struct Node{int x,id;}a[M];
    struct Q{int x,y,k,id;}q[M],tmp[M];
    int t[M],n,m,o,ans[M];
    bool cmp(Node a,Node b){return a.x<b.x;}
    void add(int x,int v){
        while(x<=n)t[x]+=v,x+=(x&-x);
    }
    int sum(int x){
        int rhs=0;
        while(x){
            rhs+=t[x];
            x-=(x&-x);
        }
        return rhs;
    }
    void sloved(int l,int r,int ql,int qr){
        int pl=ql,pr=qr,mid=(l+r)>>1;
    //    cout<<l<<" "<<r<<endl;
        if(l==r){
            for(int i=ql;i<=qr;i++)ans[q[i].id]=l;
            return ;
        }
        while(a[o+1].x<=mid&&o<n) add(a[++o].id,1);
        while(o&&a[o].x>mid)      add(a[o--].id,-1);
        for(int i=ql;i<=qr;i++){
            int res=sum(q[i].y)-sum(q[i].x-1);
    //        cout<<res<<" ";
            if(res>=q[i].k)tmp[pl++]=q[i];
            else tmp[pr--]=q[i];
        }
    //    cout<<endl;
        for(int i=ql;i<=qr;i++)q[i]=tmp[i];
        if(pl>ql)sloved(l,mid,ql,pl-1);
        if(pr<qr)sloved(mid+1,r,pr+1,qr);
    }
    int main(){
        int T;scanf("%d",&T);
        while(T--){
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i].x);
                a[i].id=i;
                t[i]=0;
            }
            o=t[0]=0;
            sort(a+1,a+n+1,cmp);
    //        for(int i=1;i<=n;i++)cout<<a[i].x<<" "<<a[i].id<<endl;
            for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k),q[i].id=i;
            sloved(-(1<<30),(1<<30),1,m);
            for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
        }
        return 0;
    }