题意

一家餐厅有(n)道菜，编号(1...n)，大家对第(i)道菜的评价值为(a_i(1le ile n))。
有(m)位顾客，第(i)位顾客的期望值为(b_i)，而他的偏好值为(x_i)。
因此，第(i)位顾客认为第(j)道菜的美味度为(b_i xor (a_j+x_i))，(xor)表示异或运算。
第(i)位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，
但由于价格等因素，他只能从第(l_i)道到第(r_i)道中选择。
请你对于每一个顾客找出最美味的菜的美味值。

数据范围

[1le nle2 imes10^5，1le mle10^5，0le a_i,b_i,x_i<10^5 ]

[1leforall ile m,1le l_ile r_ile n ]

sol

考虑按位贪心，每次在主席树上询按照异或和进行询问，时间复杂度为(O(nlogn))
其实是一道比较模板的主席树，然而我对着题目想了好久......我还是太菜啦
另:血的教训:主席树的数组真的能开多大就开多大

代码

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=19260817;
const int N=200001;
const int M=40*N;
const int base=131;
il ll read(){
	RG ll data=0,w=1;RG char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
	return data*w;
}

il void file(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}

int n,m,cnt,rt[N],s[2][M],sum[M];

#define mid ((l+r)>>1)
il void build(int &i,int l,int r){
	i=++cnt;if(l==r)return;
	build(s[0][i],l,mid);build(s[1][i],mid+1,r);
}

il void insert(int pre,int &i,int l,int r,int p){
	i=++cnt;sum[i]=sum[pre]+1;
	if(l==r)return;
	s[0][i]=s[0][pre];s[1][i]=s[1][pre];
	if(p<=mid)insert(s[0][pre],s[0][i],l,mid,p);
	else insert(s[1][pre],s[1][i],mid+1,r,p);
}

il int query(int L,int R,int l,int r,int x,int y){
	if(x<=l&&r<=y)return sum[R]-sum[L];
	RG int c=0;
	if(x<=mid)c=query(s[0][L],s[0][R],l,mid,x,y);
	if(y>mid)c+=query(s[1][L],s[1][R],mid+1,r,x,y);
	return c;
}

il int solve(int b,int x,int L,int R){
	RG int ans=0,ret=0,len=18,k;
	while(len){
		k=1<<(len-1);
		if(b&k){
			if(query(L,R,1,200000,max(1,ret-x),min(200000,ret+k-1-x)))
				ans+=k;
			else ret+=k;
		}
		else if(query(L,R,1,200000,max(1,ret+k-x),min(200000,ret+(k<<1)-1-x)))
			ret+=k,ans+=k;
		len--;
	}
	return ans;
}

int main()
{
	n=read();m=read();build(rt[0],1,200000);
	for(RG int i=1;i<=n;i++)
		insert(rt[i-1],rt[i],1,200000,read());	
	for(RG int i=1,b,x,l,r;i<=m;i++){
		b=read();x=read();l=read()-1;r=read();
		printf("%d
",solve(b,x,rt[l],rt[r]));
	}
	return 0;
}