Description

一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期

望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或

运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 

li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

Solution

按位贪心，每次通过查询一段区间是否能够取到来判断这一位能否取最优解，主席树维护

（位运算的优先级真的非常低啊，尽量都加括号）

#include
     
      #include
      
       #include
       
        #include
        
         #define N 100000#define M 200005using namespace std;int n,m,tot=0,rt[M],ls[M*20],rs[M*20],val[M*20];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;} void insert(int &idx,int last,int l,int r,int v){    ++tot,idx=tot;    ls[idx]=ls[last],rs[idx]=rs[last];    val[idx]=val[last]+1;    if(l==r)return;     int mid=(l+r)>>1;    if(v<=mid)insert(ls[idx],ls[last],l,mid,v);    else insert(rs[idx],rs[last],mid+1,r,v);}int query(int a,int b,int l,int r,int askl,int askr){    if(askl<=l&&askr>=r)return val[a]-val[b];    if(val[a]-val[b]==0)return 0;    int mid=(l+r)>>1;    if(askr<=mid)return query(ls[a],ls[b],l,mid,askl,askr);    else if(askl>mid)return query(rs[a],rs[b],mid+1,r,askl,askr);    else return query(ls[a],ls[b],l,mid,askl,askr)+query(rs[a],rs[b],mid+1,r,askl,askr);} int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)    {        int a=read();        insert(rt[i],rt[i-1],1,N,a);    }    for(int i=1;i<=m;i++)    {        int b=read(),x=read(),l=read(),r=read(),ans=0;        for(int j=17;j>=0;j--)        {　　　　　　　　　　　　　　//ans记录aj+xi能取到的最优解            int L,R;            if((1<
         
          <
          
           >j)&1)^1); else ans|=(1<
           
            >j)&1); } printf("%d\n",ans^b); } return 0;}