Luogu P3293 [SCOI2016]美味

题目描述

https://www.luogu.com.cn/problem/P3293

简要题意：给定 $n$ 个数 $a_i$ 和 $m$ 次询问，每次询问给定四个参数 $b,x,l,r$，表示从 $a[l]$ 到 $a[r]$ 选择最大的 $b\oplus (a_i+x)$，其中 $\oplus$ 表示异或

$n,m\le 2\times 10^5,0\le a,b,x\le 10^5$

Solution

我们考虑从高位到低位贪心，我们不妨假设现在已经选出的数的大小为 $ans$，那么现在要选第 $i$ 位，根据 $b$ 是否有 $i$ 这个二进制位，$a+x$ 的区间是 $[ans,ans+2^i-1]$ 或 $[ans+2^i,ans+2^{i+1}-1]$，区间查询是否有一个数的大小属于某个区间可以用主席树维护

时间复杂度 $O(n\log ^2n)$

#include <iostream>
#define maxn 200010
using namespace std;

int n, m, a[maxn];

const int N = 1 << 18; 
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
    int v, ch[2];
} T[maxn * 20]; int rt[maxn], top;
void update(int &i, int j, int l, int r, int k, int v){
	i = ++top; T[i] = T[j]; T[i].v += v;
	if (l == r) return ; int m = l + r >> 1;
	if (k <= m) update(lc, Lc, l, m, k, v);
	else update(rc, Rc, m + 1, r, k, v);
}

int query(int i, int j, int l, int r, int L, int R){
	if (l > R || r < L) return 0;
	if (L <= l && r <= R) return T[j].v - T[i].v;
	int m = l + r >> 1;
	return query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], update(rt[i], rt[i - 1], 0, N, a[i], 1);
    for (int i = 1; i <= m; ++i) {
        int b, x, l, r, ans = 0; cin >> b >> x >> l >> r; 
        for (int o = 18; ~o; --o) {
            if ((b >> o & 1) && !query(rt[l - 1], rt[r], 0, N, ans - x, ans + (1 << o) - 1 - x)) ans += 1 << o;
            else if (!(b >> o & 1) && query(rt[l - 1], rt[r], 0, N, ans + (1 << o) - x, ans + (1 << o + 1) - 1 - x)) ans += 1 << o;
        }
        cout << (ans ^ b) << "\n";
    }
    return 0;
}