主席树/线段树模拟归并排序+二分答案（好题）——hdu多校第4场08

雨点打透心脏的1/2处 2023-10-11 09:12 8阅读 0赞

用主席树写起来跑的快一点，而且也很傻比，二分答案，即二分那个半径就行

主席树求的是区间<=k的个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 1000005
    int a[maxn],n,m;
    
    struct Node{
         int lc,rc,v;}t[maxn*25];
    int rt[maxn],tot;
    int update(int last,int l,int r,int pos){
        int now=++tot;
        t[now]=t[last];
        t[now].v++;
        if(l==r)return now;
        int m=l+r>>1;
        if(pos<=m)
            t[now].lc=update(t[last].lc,l,m,pos);
        else t[now].rc=update(t[last].rc,m+1,r,pos);
        return now;
    }
    int query(int st,int ed,int L,int R,int l,int r){
        if(L>R)return 0;
        if(L<=l && R>=r)return t[ed].v-t[st].v;
        int m=l+r>>1,res=0;
        if(L<=m)res+=query(t[st].lc,t[ed].lc,L,R,l,m);
        if(R>m)res+=query(t[st].rc,t[ed].rc,L,R,m+1,r);
        return res;
    }
    int build(int l,int r){
        int now=++tot;
        t[now].lc=t[now].rc=t[now].v=0;
        if(l==r)return now;
        int m=l+r>>1;
        t[now].lc=build(l,m);
        t[now].rc=build(m+1,r);
        return now;
    }
    void init(){
        memset(rt,0,sizeof rt);
        memset(t,0,sizeof t);
        tot=0;
    }
    
    int main(){
        int t;cin>>t;
        while(t--){
            init();
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
            rt[0]=build(1,n);
            for(int i=1;i<=n;i++)
                rt[i]=update(rt[i-1],1,2000000,a[i]);
            
            int ans=0,l,r,p,k;
            while(m--){
                scanf("%d%d%d%d",&l,&r,&p,&k);
                l^=ans,r^=ans,p^=ans,k^=ans;
                
                int L=0,R=1000000,mid;ans=0;
                while(L<=R){
                    mid=L+R>>1;
                    int res1=query(rt[l-1],rt[r],1,mid+p,1,2000000);
                    int res2=query(rt[l-1],rt[r],1,p-mid-1,1,2000000);
                    if(res1-res2>=k)
                        ans=mid,R=mid-1;
                    else L=mid+1;
                }
                cout<<ans<<'\n';
            }
        }
    }

线段树的话就要模拟一下归并排序的过程，即线段树结点维护的是区间的有序序列

然后还是二分答案，然后查询的是区间\[l,r\]范围内**在\[p-mid,p+mid\]范围内的数个数**，要特别注意查询的方式

int res1=lower_bound(seg[rt].begin(),seg[rt].end(),v1)-seg[rt].begin(); int res2=upper_bound(seg[rt].begin(),seg[rt].end(),v2)-seg[rt].begin();//上界一定要用upper_bound!
            return res2-res1;

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define maxn 100005
    int n,k,l,r,ans,p,m,a[maxn];
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    vector<int>seg[maxn<<2];
    void pushup(int rt){
        int s=seg[rt<<1].size(),t=seg[rt<<1|1].size(),i=0,j=0;
        while(i!=s && j!=t){
            if(seg[rt<<1][i]<=seg[rt<<1|1][j])
                seg[rt].push_back(seg[rt<<1][i]),i++;
            else seg[rt].push_back(seg[rt<<1|1][j]),j++;
        }
        while(i!=s){
            seg[rt].push_back(seg[rt<<1][i]);
            i++;
        }
        while(j!=t){
            seg[rt].push_back(seg[rt<<1|1][j]);
            j++;
        }
    }
    
    void build(int l,int r,int rt){
        seg[rt].clear();
        if(l==r){
            seg[rt].push_back(a[l]);return;
        }
        int m=l+r>>1;
        build(lson);build(rson);
        pushup(rt);
    }
    int query(int L,int R,int v1,int v2,int l,int r,int rt){
        if(L<=l && R>=r){
            int res1=lower_bound(seg[rt].begin(),seg[rt].end(),v1)-seg[rt].begin();
            int res2=upper_bound(seg[rt].begin(),seg[rt].end(),v2)-seg[rt].begin();
            return res2-res1;
        }
        int m=l+r>>1,res=0;
        if(L<=m)res+=query(L,R,v1,v2,lson);
        if(R>m)res+=query(L,R,v1,v2,rson);
        return res;
    }
    
    int judge(int mid){ 
        int res=0;//查找半径是mid 
        res=query(l,r,p,p+mid,1,n,1);
        if(res>=k)return 1;
        res+=query(l,r,p-mid,p-1,1,n,1);
        if(res>=k)return 1;
        return 0;
    }
    
    int main(){
        int t;cin>>t;
        while(t--){
             n=k=l=r=ans=p=m=0;
            
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
            build(1,n,1);
                
            while(m--){
                scanf("%d%d%d%d",&l,&r,&p,&k);
                l^=ans,r^=ans,p^=ans,k^=ans;
                int L=0,R=10000000,mid;
                ans=0;
                while(L<=R){
        //二分半径 
                    mid=L+R>>1; 
                    if(judge(mid))
                        ans=mid,R=mid-1;
                    else L=mid+1; 
                }
                cout<<ans<<'\n';
            }
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11279358.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif