C++14(g++5.4) 解法, 执行用时: 1359ms, 内存消耗: 45904K, 提交时间: 2020-01-14 10:51:40

#include<bits/stdc++.h>
using namespace std;
const int MX=2e5+9;
struct node{
    int l,r,cnt;
}p[MX*20];
int tr[MX],n,m,sz,val;

void init(){
    sz=0;
    memset(tr,0,sizeof(tr));
}

void update(int old,int &now,int l,int r,int pos){
    now=++sz;
    p[now]=p[old];
    p[now].cnt++;
    if( l==r )
        return ;
    int mid=(l+r)>>1;
    if( pos<=mid )
        update(p[old].l,p[now].l,l,mid,pos);
    else
        update(p[old].r,p[now].r,mid+1,r,pos);
}

int que(int old,int now,int L,int R,int l,int r){
    if( l<=L && R<=r )
        return p[now].cnt-p[old].cnt;
    int mid=(L+R)>>1,ans=0;
    if( l<=mid )
        ans+=que(p[old].l,p[now].l,L,mid,l,r);
    if( mid<r )
        ans+=que(p[old].r,p[now].r,mid+1,R,l,r);
    return ans;
}

int main()
{
    //freopen("input.txt","r",stdin);
    init();
    scanf("%d %d",&n,&m);
    for( int i=1 ; i<=n ; i++ ){
        scanf("%d",&val);
        update(tr[i-1],tr[i],0,MX,val);
    }
    while( m-- ){
        int b,x,l,r,ans=0;
        scanf("%d %d %d %d",&b,&x,&l,&r);
        for( int i=17 ; i>=0  ; i-- ){
            if( (b>>i) & 1 ){
                int L=min(max(0,(ans-x)+0),MX);
                int R=min(max(0,(ans-x)+((1<<i)-1)),MX);
                if( que(tr[l-1],tr[r],0,MX,L,R) )
                    continue;
                else
                    ans|=(1<<i);
            }
            else{
                int L=min(max(0,(ans-x)+(1<<i)),MX);
                int R=min(max(0,(ans-x)+((1<<(i+1))-1)),MX);
                if( que(tr[l-1],tr[r],0,MX,L,R) )
                    ans|=(1<<i);
            }
        }
        printf("%d\n",ans^b);
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 933ms, 内存消耗: 43416K, 提交时间: 2021-08-21 21:10:38

#include<bits/stdc++.h>
using namespace std;
/*
主席树区间查询
贪心 
*/
const int N=2e5+5;
const int maxr=1e5;
struct node{
	int l;
	int r;
	int sum;
}p[N*40];
int cnt=0,rt[N];
void upd(int l,int r,int y,int &x,int pos){
	p[++cnt]=p[y];
	p[cnt].sum++;
	x=cnt;
	if(l==r)return; 
	int mid=l+r>>1;
	if(pos<=mid)upd(l,mid,p[y].l,p[x].l,pos);
	else upd(mid+1,r,p[y].r,p[x].r,pos);
}
int query(int l,int r,int y,int x,int L,int R){
	if(p[x].sum-p[y].sum<=0)return 0;
	if(l<=L&&r>=R){
		return p[x].sum-p[y].sum;
	}
	int mid=L+R>>1,ans=0;
	if(l<=mid)ans+=query(l,r,p[y].l,p[x].l,L,mid);
	if(r>mid)ans+=query(l,r,p[y].r,p[x].r,mid+1,R);
	return ans;
}
int main(){
	int n,m,x,b,l,r;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		upd(0,maxr,rt[i-1],rt[i],x);
	}
	int ans;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&b,&x,&l,&r);
		ans=0;
		for(int j=20;j>=0;j--){//贪心选择当前位最高 查询区间内是否存在a+x转化为区间-x是否存在a 
			if(((b>>j)&1)&&!query(ans-x,ans+(1<<j)-1-x,rt[l-1],rt[r],0,maxr))ans+=(1<<j);
			else if(!((b>>j)&1)&&query(ans+(1<<j)-x,ans+(1<<j+1)-1-x,rt[l-1],rt[r],0,maxr))ans+=(1<<j);
		}
		printf("%d\n",b^ans);
	}
	return 0;
}