"Scoi2016" delicious problem solution

link ：#2016. 「SCOI2016」 delicious - subject - LibreOJ (loj.ac)

The question ： Given a sequence , Multiple query intervals $[l,r]$ The number in $a_i+x$ And $b$ XOR maximum , Give out... Every time you ask $b,x,l,r$.

Answer key ： If it doesn't come with this x , It's a persistent 01trie The naked question of , But add x after , It is difficult to judge a particular number by bits . But you can judge a range , Greedy from high to low . Each query if this bit gets and b Whether there is such a number in the reverse value , If it exists, take it like this , Or take it in reverse . At the same time, we need to add x The influence of . Judge whether there is a number in a value range of a certain interval , Obviously, the chairman tree can be maintained . Complexity $O(nlognlogw)$ ,w Value range .

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int maxn=2e5+5;

int a[maxn],n,m,b,x,l,r,mx;
int ls[maxn*20],rs[maxn*20],sum[maxn*20],rt[maxn],now;

void update(int u,int&v,int l,int r,int pos)
{
    
	v=++now,ls[v]=ls[u],rs[v]=rs[u],sum[v]=sum[u]+1;
	if(l==r)return;
	int mid=l+r>>1;
	if(pos<=mid)update(ls[u],ls[v],l,mid,pos);
	else update(rs[u],rs[v],mid+1,r,pos);
	return;
}

int query(int u,int v,int l,int r,int ql,int qr)
{
    
	if(ql<=l&&r<=qr)return sum[v]-sum[u];
	int mid=l+r>>1,res=0;
	if(ql<=mid)res+=query(ls[u],ls[v],l,mid,ql,qr);
	if(mid<qr)res+=query(rs[u],rs[v],mid+1,r,ql,qr);
	return res;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m; mx=2e5;
	for(int i=1;i<=n;i++)
	{
    
		cin>>a[i],update(rt[i-1],rt[i],1,mx,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
    
		cin>>b>>x>>l>>r;
		int ans=0,res=0;
		for(int j=17;j>=0;j--)
		{
    
			int p=(b>>j&1)^1;
			if(query(rt[l-1],rt[r],1,mx,res+p*(1<<j)-x,res+(1+p)*(1<<j)-1-x))
			{
    
				ans+=1<<j,res+=p*(1<<j);
			}
			else res+=(p^1)*(1<<j);
		}
		cout<<ans<<"\n";
	}
	return 0;
}