Description

给你一个长度为 \(n\) 的序列 \(A\) 。 \(m\) 组询问 \((b,x,l,r)\) 询问 \[\max_{i=l}^r b\oplus (A_i+x)\]

\(1\leq n\leq 2\cdot 10^5,1\leq m,A_i,b,x\leq 10^5\)

Solution

还是按位贪心。

先找到在区间内是否有满足的当前位的 \(A\) 值。再逐步缩小范围查找。

具体为：

假设我们已经处理到 \(b\) 的第 \(i\) 位（转换成二进制），假设是 \(1\) （ \(0\) 同理）。

那么我们只需要查找是否存在 \(A_j+x\) 使得其二进制第 \(i\) 位数字是 \(0\) ，显然我们已经处理了前 \(i-1\) 位了， \(i\) 位前的限制为 \(last\) ，那么我们需要查找的数的大小就是在区间 \([last-x,last+(1<<i)-1-x]\) ，手算一下就知道这个区间里的数字的第 \(i\) 位加了 \(x\) 后就都是 \(0\) 。

那么现在我们就是要在 \(A_l\sim A_r\) 中找出是否存在于 \([last-x,last+(1<<i)-1-x]\) 的数字，两个区间范围限制，用主席树模板一套就好了。

Code

//It is made by Awson on 2018.3.4#include 
    
     #define LL long long#define dob complex
     
      #define Abs(a) ((a) < 0 ? (-(a)) : (a))#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))#define writeln(x) (write(x), putchar('\n'))#define lowbit(x) ((x)&(-(x)))using namespace std;const int N = 2e5;void read(int &x) {    char ch; bool flag = 0;    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());    x *= 1-2*flag;}void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }int n, m, a, L, R, b, x, bin[20];struct Segment_tree {    int root[N+5], ch[N*50+5][2], key[N*50+5], pos;    int cpynode(int o) {++pos, ch[pos][0] = ch[o][0], ch[pos][1] = ch[o][1], key[pos] = key[o]; return pos; }    void insert(int &o, int l, int r, int loc) {    o = cpynode(o); ++key[o];    if (l == r) return; int mid = (l+r)>>1;    if (loc <= mid) insert(ch[o][0], l, mid, loc);    else insert(ch[o][1], mid+1, r, loc);    }    int query(int o1, int o2, int l, int r, int a, int b) {    if (a <= l && r <= b) return key[o2]-key[o1]; int mid = (l+r)>>1;    int c1 = 0, c2 = 0;    if (a <= mid) c1 = query(ch[o1][0], ch[o2][0], l, mid, a, b);    if (b > mid) c2 = query(ch[o1][1], ch[o2][1], mid+1, r, a, b);    return c1+c2;    }}T;void work() {    read(n), read(m); bin[0] = 1; for (int i = 1; i <= 18; i++) bin[i] = bin[i-1]<<1;    for (int i = 1; i <= n; i++) read(a), T.insert(T.root[i] = T.root[i-1], 0, N, a);    while (m--) {    read(b), read(x), read(L), read(R);    int last = 0, ans = 0;    for (int i = 18; i >= 0; i--) {        int tmp = last+((bin[i]&b)^bin[i]);        int l = Max(tmp-x, 0), r = Min(N, tmp-x+bin[i]-1);        if (l > r) {last += (bin[i]&b); continue; }        if (T.query(T.root[L-1], T.root[R], 0, N, l, r)) last = tmp, ans += bin[i];        else last += (bin[i]&b);    }    writeln(ans);    }}int main() {    work(); return 0;}