题目
一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期
望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或
运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第
li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。
输入格式
第1行，两个整数，n，m，表示菜品数和顾客数。
第2行，n个整数，a1，a2，...，an，表示每道菜的评价值。
第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。
1≤n≤2×105，1≤li≤ri≤n(1≤i≤m)；1≤m≤10^5
输出格式
输出 m 行，每行 1 个整数，ymax ，表示该位顾客选择的最美味的菜的美味值。
输入样例
4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4
输出样例
9
7
6
7
题解
很棒的思想
从高位开始枚举每一位，每个时刻解的值都是一个连续的区间，用主席树区间和判断区间内是否存在这样的值
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 200005,maxm = 4000005,MAX = 100000,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int sum[maxm],ls[maxm],rs[maxm],rt[maxn],cnt;
int n,m,a[maxn],bin[20];
void add(int& u,int pre,int l,int r,int pos){
sum[u = ++cnt] = sum[pre] + 1;
ls[u] = ls[pre]; rs[u] = rs[pre];
if (l == r) return;
int mid = l + r >> 1;
if (mid >= pos) add(ls[u],ls[pre],l,mid,pos);
else add(rs[u],rs[pre],mid + 1,r,pos);
}
int query(int u,int v,int l,int r,int L,int R){
if (l >= L && r <= R) return sum[u] - sum[v];
int mid = l + r >> 1;
if (mid >= R) return query(ls[u],ls[v],l,mid,L,R);
if (mid < L) return query(rs[u],rs[v],mid + 1,r,L,R);
return query(ls[u],ls[v],l,mid,L,R) + query(rs[u],rs[v],mid + 1,r,L,R);
}
int main(){
bin[0] = 1;
for (int i = 1; i <= 18; i++) bin[i] = bin[i - 1] << 1;
n = read(); m = read();
REP(i,n){
a[i] = read();
add(rt[i],rt[i - 1],0,MAX,a[i]);
}
int b,x,L,R,l,r,tmp,ans;
while (m--){
b = read(); x = read(); L = read(); R = read();
ans = 0;
for (int i = 17; i >= 0; i--){
if (b & bin[i]){
l = max(ans - x,0);
r = min(max(ans + bin[i] - 1 - x,0),MAX);
if (l > MAX || r < 0) {ans |= bin[i]; continue;}
l = max(l,0);
r = min(r,MAX);
tmp = query(rt[R],rt[L - 1],0,MAX,l,r);
if (!tmp) ans |= bin[i];
}
else {
l = ans + bin[i] - x;
r = ans + bin[i + 1] - 1 - x;
if (l > MAX || r < 0) continue;
l = max(l,0);
r = min(r,MAX);
tmp = query(rt[R],rt[L - 1],0,MAX,l,r);
if (tmp) ans |= bin[i];
}
}
printf("%d\n",b ^ ans);
}
return 0;
}