Description
一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。
因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。
第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 li 道到第 ri 道中选择。
请你帮助他们找出最美味的菜。
Input
第1行，两个整数，n，m，表示菜品数和顾客数。
第2行，n个整数，a1，a2，...，an，表示每道菜的评价值。
第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。
1≤n≤2×10^5，0≤ai,bi,xi＜10^5，1≤li≤ri≤n(1≤i≤m)；1≤m≤10^5
Output
输出 m 行，每行 1 个整数，ymax ，表示该位顾客选择的最美味的菜的美味值。
Sample Input
4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4
Sample Output
9
7
6
7
7
6
7
Solution
感觉自己有点傻……
考虑按位贪心。
首先要明确一个东西，我们最终要输出的是$ans~xor~b$，所以贪$ans$的时候要注意一下。
若$b$的第$i$位为$1$，那么如果在区间$[ans-x,(ans|((1<<i)-1))-x]$如果没有数的话，$ans$的第$i$位就置为$1$，也就是对应着答案这里这一位选不上，成$0$了。
若$b$的第$i$位为$0$的情况同理……我也说不太清楚……看看代码感性理解一下吧……QAQ
Code
#include<iostream>
#include<cstdio>
#define N (200009)
using namespace std; struct Sgt{int ls,rs,val;}Segt[N<<];
int n,m,b,x,l,r,L,R,ans,sgt_num,a[N],Root[N]; int Update(int pre,int l,int r,int x)
{
int now=++sgt_num;
Segt[now]=Segt[pre]; Segt[now].val++;
if (l==r) return now;
int mid=(l+r)>>;
if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x);
else Segt[now].rs=Update(Segt[now].rs,mid+,r,x);
return now;
} int Query(int u,int v,int l,int r,int l1,int r1)
{
if (l>r1 || r<l1) return ;
if (l1<=l && r<=r1) return Segt[v].val-Segt[u].val;
int mid=(l+r)>>;
return Query(Segt[u].ls,Segt[v].ls,l,mid,l1,r1)+Query(Segt[u].rs,Segt[v].rs,mid+,r,l1,r1);
} int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i)
scanf("%d",&a[i]), Root[i]=Update(Root[i-],,1e5,a[i]);
while (m--)
{
ans=;
scanf("%d%d%d%d",&b,&x,&l,&r);
for (int i=; i>=; --i)
if (b&(<<i))
{
L=max(,ans-x); R=(ans|((<<i)-))-x;
if (!Query(Root[l-],Root[r],,1e5,L,R)) ans|=(<<i);
}
else
{
ans|=(<<i);
L=max(,ans-x); R=(ans|((<<i)-))-x;
if (!Query(Root[l-],Root[r],,1e5,L,R)) ans^=(<<i);
}
printf("%d\n",ans^b);
}
}