[bzoj4571] [loj#2016] [Scoi2016] 美味

Description

一家餐厅有 (n) 道菜，编号 (1)...(n) ，大家对第 (i) 道菜的评价值为 (ai)( (1 leq i leq 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 leq n leq 2 times 10^5)，(0 leq ai,bi,xi＜10^5) ，(1 leq li leq ri leq n(1 leq i leq m))；(1 leq m leq 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

Sample Output

9

7

6

7

想法

第一眼看，可持久化 (trie) 啊
后来发现异或的是 (ai+xi) ，有点麻烦
但没关系，换成可持久化权值线段树，道理一样，从高位到低位贪心枚举即可。
复杂度 (O(nlog^2 n))

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int read(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}

const int N = 200005;
const int MAX = 100000;

int n,m;

int root[N],cnt,ch[N*20][2],s[N*20];
void ins(int x,int y,int l,int r,int c){
    s[x]=s[y]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(c<=mid) ins(ch[x][0]=++cnt,ch[y][0],l,mid,c),ch[x][1]=ch[y][1];
    else ins(ch[x][1]=++cnt,ch[y][1],mid+1,r,ch[x][0]=ch[y][0];
}
int num(int x,int L,int R){
    if(L<=l && r<=R) return s[x]-s[y];
    int mid=(l+r)>>1,ret=0;
    if(L<=mid) ret+=num(ch[x][0],L,R);
    if(R>mid) ret+=num(ch[x][1],R);
    return ret;
}

int main()
{
    n=read(); m=read();
    for(int i=1;i<=n;i++) ins(root[i]=++cnt,root[i-1],1,MAX,read());
    
    int b,x,r;
    while(m--){
        b=read(); x=read(); l=read(); r=read();
        int cur=0,ll,rr,id;
        for(int i=18;i>=0;i--){
            id= (b&(1<<i)) ? 1 : 0 ; 
            if(!id) ll=cur+(1<<i)-x,rr=cur+(2<<i)-1-x;
            else ll=cur-x,rr=cur+(1<<i)-1-x;
            if(rr>0 && ll<=MAX && num(root[r],root[l-1],rr)>0)
                cur+=(id^1)<<i;
            else cur+=id<<i;
        }
        printf("%dn",b^cur);
    }
    
    return 0;
}