可持久化字典树
例题传送门：异或运算
还不错的题
既然要异或运算，我们可以想到按位枚举，用字典树去存。
既然要找第 \(k\) 大，我们可以想到主席树。
所以这题就是：可持久化字典树
考虑到这题 \(n,p\) 较小，可以直接枚举，而 \(m\) 较大，我们可以用可持久化字典树去存 \(y_i\)，查询的时候就模拟字典树的查询，考虑第 \(i\) 位是 \(1\) 还是 \(0\)，时间复杂度 \(O(np \log m)\)，可以接受。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1050,M=300050;
ll n,m,p;
ll x[N],y[M];
struct jgt
{
ll ch[2],cnt;
}tr[M*40];
ll rt[M],tot;
void add(ll &now,ll last,ll x,ll sz)
{
now=++tot;
tr[now]=tr[last];
tr[now].cnt++;
if(sz<0) return ;
if((x&(1<<sz))) add(tr[now].ch[1],tr[last].ch[1],x,sz-1);
else add(tr[now].ch[0],tr[last].ch[0],x,sz-1);
}
ll now[N],last[N];
ll updQ(ll lx,ll rx,ll ly,ll ry,ll k)
{
for(ll i=lx;i<=rx;i++)
{
now[i]=rt[ry];
last[i]=rt[ly-1];
}
ll re=0,cnt;
bool flag;
for(ll i=31;i>=0;i--)
{
cnt=0;
for(ll j=lx;j<=rx;j++)
{
if((x[j]&(1<<i))) cnt=cnt+tr[tr[now[j]].ch[0]].cnt-tr[tr[last[j]].ch[0]].cnt;
else cnt=cnt+tr[tr[now[j]].ch[1]].cnt-tr[tr[last[j]].ch[1]].cnt;
}
if(k<=cnt)
{
flag=true;
re=((re<<1)|1);
}
else
{
k-=cnt;
flag=false;
re=(re<<1);
}
for(ll j=lx;j<=rx;j++)
{
if(flag)
{
if((x[j]&(1<<i))) now[j]=tr[now[j]].ch[0],last[j]=tr[last[j]].ch[0];
else now[j]=tr[now[j]].ch[1],last[j]=tr[last[j]].ch[1];
}
else
{
if((x[j]&(1<<i))) now[j]=tr[now[j]].ch[1],last[j]=tr[last[j]].ch[1];
else now[j]=tr[now[j]].ch[0],last[j]=tr[last[j]].ch[0];
}
}
}
return re;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&x[i]);
for(ll i=1;i<=m;i++)
{
scanf("%lld",&y[i]);
add(rt[i],rt[i-1],y[i],31);
}
scanf("%lld",&p);
ll t1,t2,t3,t4,t5;
for(ll i=1;i<=p;i++)
{
scanf("%lld %lld %lld %lld %lld",&t1,&t2,&t3,&t4,&t5);
printf("%lld\n",updQ(t1,t2,t3,t4,t5));
}
return 0;
}