题意

题目链接

做法

一个很新鲜的 idea，由于直接建 01trie 没法支持修改，不妨考虑另类做法：

枚举答案 $\mathrm{xor}$ $b$（即枚举 $x_{i}+a_{j}$）的二进制每一位是 $0$ 还是 $1$ ，即对于最高位第 $t$ 位，如果我想要这一位是 $0$（因为 $b$ 的这一位是 $1$ ），那么就判断 $[l,r]$ 区间是否有 $[0,2^{t}-1]$ 的数字，后面的位类似。

至于判断区间是否存在某个区间的数字，直接用动态开点线段树搞就行了。

时间复杂度：$O(n\log^2{\mathrm{V}})$

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#define  N  210000
#define  NN  4100000
using  namespace  std;
struct  node
{
	int  l,r,c/*数字个数*/;
}tr[NN];int  len,rt[N];
inline  void  updata(int  x){tr[x].c+=tr[tr[x].l].c+tr[tr[x].r].c;}
void  link(int  &x,int  l,int  r,int  k)
{
	if(!x)x=++len;
	tr[x].c++;
	if(l==r)return  ;
	int  mid=(l+r)>>1;
	if(k<=mid)link(tr[x].l,l,mid,k);
	else  link(tr[x].r,mid+1,r,k);
}
void  mer(int  &x,int  y)
{
	if(!x  ||  !y){x=x+y;return  ;}
	tr[x].c+=tr[y].c;
	mer(tr[x].l,tr[y].l);mer(tr[x].r,tr[y].r);
}
bool  query(int  x,int  y,int  l,int  r,int  ll,int  rr)
{
	if(tr[x].c==tr[y].c)return  0;
	else  if(l==ll  &&  r==rr)return  tr[x].c-tr[y].c>0;
	int  mid=(l+r)>>1;
	if(rr<=mid)return  query(tr[x].l,tr[y].l,l,mid,ll,rr);
	else  if(mid<ll)return  query(tr[x].r,tr[y].r,mid+1,r,ll,rr);
	else
	{
		if(!query(tr[x].l,tr[y].l,l,mid,ll,mid))return  query(tr[x].r,tr[y].r,mid+1,r,mid+1,rr);
		return  1;
	}
}
int  n,m,limit=262143;
int  main()
{
	scanf("%d%d",&n,&m);
	for(int  i=1;i<=n;i++)
	{
		int  x;scanf("%d",&x);
		link(rt[i],0,limit,x);
	}
	for(int  i=2;i<=n;i++)mer(rt[i],rt[i-1]);
	for(int  i=1;i<=m;i++)
	{
		int  b,x,l,r;scanf("%d%d%d%d",&b,&x,&l,&r);
		int  ans=0;
		for(int  j=17;j>=0;j--)
		{
			int  ll=ans,rr=ans;
			if(b&(1<<j))rr+=(1<<j)-1;//有
			else  ll+=(1<<j),rr+=(1<<(j+1))-1;//没有 
			ll-=x;rr-=x;
			int  shit;
			if(ll<0  &&  rr<0)shit=0;//完全不行
			else
			{
				if(ll<0)ll=0;
				shit=query(rt[r],rt[l-1],0,limit,ll,rr);
			}
			ans|=(b&(1<<j))^(shit<<j); 
		}
		printf("%d\n",ans^b);
	}
	return  0;
}