题目地址：洛谷：【P3293】[SCOI2016]美味 – 洛谷、BZOJ：Problem 4571. — [Scoi2016]美味

题目描述

一家餐厅有 n 道菜，编号 1…n ，大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。
第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

题意简述

给一个长为n的数列a，每次查询给b、x、l、r，查询使得b xor (ai + x)最大的a数列中[l, r]这些数字中的ai。

输入输出格式

输入格式：
第1行，两个整数，n，m，表示菜品数和顾客数。
第2行，n个整数，a1，a2，…，an，表示每道菜的评价值。
第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

输出格式：
输出 m 行，每行 1 个整数，ymax ，表示该位顾客选择的最美味的菜的美味值。

输入输出样例

输入样例#1：

4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4

输出样例#1：

9 
7 
6 
7

说明

对于所有测试数据，1<=n<=2*10^5，0<=ai,bi,xi＜10^5，1<=li<=ri<=n(1<=i<=m)；1<=m<=10^5

题解

参考资料：[BZOJ4571][SCOI2016]美味 – 租酥雨 – 博客园
异或相关信息用Trie树方便，区间无修查询用主席树方便。这里二选一，我们选择主席树。
那么主席树应该怎么做呢？我们依然按位贪心，让bi尽量跟(aj + xi)每一位都不同，假设枚举到代表2^i的一位，且假设ans是之前已经确定的位加起来的总和，那么其实当该位为1的时候，枚举更低的位数构成的集合是一个长为2^i的区间 [ans, ans + 2^i - 1] ，我们只需要在主席树上查这个区间内有没有数字就好了。
总复杂度是O(n \log^2 n)。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

struct Node {
    int lch, rch, val;
} tr[MAXN * 100];
int rt[MAXN], tot;

inline void insert(int &o, int l, int r, int x) {
    tr[++tot] = tr[o]; o = tot;
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline int query(int o1, int o2, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) return tr[o2].val - tr[o1].val;
    int res = 0;
    int mid = (l + r) >> 1;
    if(ll <= mid) res += query(tr[o1].lch, tr[o2].lch, l, mid, ll, rr);
    if(rr > mid) res += query(tr[o1].rch, tr[o2].rch, mid + 1, r, ll, rr);
    return res;
}

int n, m, a[MAXN];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); 
        rt[i] = rt[i - 1];
        insert(rt[i], 0, 100000, a[i]);
    }
    for(int i = 1, b, x, l, r; i <= m; i++) {
        b = readint(); x = readint(); l = readint(); r = readint();
        int ans = 0;
        for(int i = 19; i >= 0; i--) {
            int ql, qr, now;
            if(b & (1 << i)) {
                ql = ans; qr = ans + (1 << i) - 1; now = 0;
            } else {
                ql = ans + (1 << i); qr = ans + (1 << (i + 1)) - 1; now = 1;
            }
            if(!query(rt[l - 1], rt[r], 0, 100000, 
                std::max(0, ql - x), std::min(qr - x, 100000))) now ^= 1;
            ans += now << i;
        }
        printf("%d\n", ans ^ b);
    }
    return 0;
}