主席树/线段树模拟归并排序+二分答案（好题）—

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

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

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000005

int a[maxn],n,m;

struct Node{int lc,rc,v;}t[maxn*];

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>>;

    if(pos<=m)

        t[now].lc=update(t[last].lc,l,m,pos);

    else t[now].rc=update(t[last].rc,m+,r,pos);

    return now;

}

int query(int st,int ed,int L,int R,int l,int r){

    if(L>R)return ;

    if(L<=l && R>=r)return t[ed].v-t[st].v;

    int m=l+r>>,res=;

    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+,r);

    return res;

}

int build(int l,int r){

    int now=++tot;

    t[now].lc=t[now].rc=t[now].v=;

    if(l==r)return now;

    int m=l+r>>;

    t[now].lc=build(l,m);

    t[now].rc=build(m+,r);

    return now;

}

void init(){

    memset(rt,,sizeof rt);

    memset(t,,sizeof t);

    tot=;

}

int main(){

    int t;cin>>t;

    while(t--){

        init();

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        rt[]=build(,n);

        for(int i=;i<=n;i++)

            rt[i]=update(rt[i-],,,a[i]);

        int ans=,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=,R=,mid;ans=;

            while(L<=R){

                mid=L+R>>;

                int res1=query(rt[l-],rt[r],,mid+p,,);

                int res2=query(rt[l-],rt[r],,p-mid-,,);

                if(res1-res2>=k)

                    ans=mid,R=mid-;

                else L=mid+;

            }

            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<<];

void pushup(int rt){

    int s=seg[rt<<].size(),t=seg[rt<<|].size(),i=,j=;

    while(i!=s && j!=t){

        if(seg[rt<<][i]<=seg[rt<<|][j])

            seg[rt].push_back(seg[rt<<][i]),i++;

        else seg[rt].push_back(seg[rt<<|][j]),j++;

    }

    while(i!=s){

        seg[rt].push_back(seg[rt<<][i]);

        i++;

    }

    while(j!=t){

        seg[rt].push_back(seg[rt<<|][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>>;

    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>>,res=;

    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=;//查找半径是mid

    res=query(l,r,p,p+mid,,n,);

    if(res>=k)return ;

    res+=query(l,r,p-mid,p-,,n,);

    if(res>=k)return ;

    return ;

}

int main(){

    int t;cin>>t;

    while(t--){

         n=k=l=r=ans=p=m=;

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        build(,n,);

        while(m--){

            scanf("%d%d%d%d",&l,&r,&p,&k);

            l^=ans,r^=ans,p^=ans,k^=ans;

            int L=,R=,mid;

            ans=;

            while(L<=R){//二分半径

                mid=L+R>>;

                if(judge(mid))

                    ans=mid,R=mid-;

                else L=mid+;

            }

            cout<<ans<<'\n';

        }

    }

}

巴特西

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

最新文章

热门文章