[THUSC2015] 异或运算 题解

学到新思路了：求解 \(k\) 大值时，可以将所有元素放一块一起跑。

考虑到 \(n,q\) 奇小无匹，我们便可以制造一个 \(O(qn\log V)\) 的代码。

那么对于我们不想在时间复杂度中出现的 \(m\)，我们直接把他扔进可持久化 \(Trie\) 中销赃。

再根据刚才那个思路，将 \([u,d]\) 中所有点扔进可持久化 \(Trie\) 里递归。

时间复杂度 \(O((m+qn)\log V)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int M=1e7+5,K=1005;
int n,m,a[K],nx[K],ny[K],tot;
int q,rt[N],ch[M][2],val[M];
void add(int &x,int y,int v,int id){
	if(!x) x=++tot;
	val[x]=val[y]+1;
	if(id<0) return;
	int c=((v>>id)&1);
	ch[x][c^1]=ch[y][c^1];
	add(ch[x][c],ch[y][c],v,id-1);
}int super_ans(int l,int r,int id,int k){
	if(id<0) return 0;int num=0;
	for(int i=l;i<=r;i++){
		int c=1-((a[i]>>id)&1);
		num+=val[ch[nx[i]][c]]-val[ch[ny[i]][c]];
	}for(int i=l;i<=r;i++){
		int c=((a[i]>>id)&1)^(num>=k);
		nx[i]=ch[nx[i]][c],ny[i]=ch[ny[i]][c];
	}return super_ans(l,r,id-1,k-(num<k)*num)+((num>=k)<<id);
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,x;i<=m;i++)
		cin>>x,add(rt[i],rt[i-1],x,30);
	cin>>q;
	while(q--){
		int u,d,l,r,k;cin>>u>>d>>l>>r>>k;
		for(int i=u;i<=d;i++)
			ny[i]=rt[l-1],nx[i]=rt[r];
		cout<<super_ans(u,d,30,k)<<"\n";
	}return 0;
}