这个题目的思路比较清奇？
一直想着用 Trie 来做，然而……
首先按位贪心是显然的，如果没有 \(x_i\) 的限制，可持久化 Trie 完事。
但是现在有了一个偏移量 \(x_i\)，直接在 Trie 的结构上不太好做。
那么——我们可以用两只 \(\log\) 来解决，一只用来按位贪心，一只用来检查是否合法。
后者使用主席树。
即，从高位到低位枚举，然后每次在主席树上检查 \([l_i,r_i]\) 区间内是否有如此的数（查询时减去 \(x_i\)）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int N = 2e5;
const int C = 1e5;
const int LG = 18;
int n,m,a[N + 5],ans;
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],++seg[p = tot].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),insert(a[i],rt[i] = rt[i - 1],0,C);
int b,x,l,r;
while(m--)
{
scanf("%d%d%d%d",&b,&x,&l,&r),ans = 0;
for(register int i = LG;i;--i)
{
ans += ((((b >> i - 1) & 1) ^ 1) << i - 1);
if(!(query(ans - x,ans + (1 << i - 1) - 1 - x,rt[r],0,C) - query(ans - x,ans + (1 << i - 1) - 1 - x,rt[l - 1],0,C)))
ans ^= 1 << i - 1;
}
printf("%d\n",ans ^ b);
}
}