「bzoj4103」「THUSC2015」异或运算 - 可持久化trie树

题目大意

    给定长度为$n$的数列$X={x_1,x_2,\ldots,x_n}$和长度为$m$的数列$Y={y_1,y_2,\ldots,y_m}$，令矩阵$A$中第$i$行第$j$列的值$A_{ij}=x_i\bigoplus y_j$，每次询问给定矩形区域$i\in[u,d],j\in[l,r]$，找出第$k$大的$A_{ij}$。
    $0<=x_i,y_j\lt2^{31},1\le u\le d\le n\le1000,1\le l\le r\le m\le300000$

---

题目分析

第一眼不可做题。

看看数据范围，发现$n,m$不同阶？
这意味着$O(qn\cdot31)$是可接受的。

于是把询问矩阵拆成$O(n)$个区间，放在可持久化trie树上查询$k$大。
查询过程类似主席树查$k$大。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=300005,maxb=35;

struct Query {
	int l,r,v;
	Query(int _l=0,int _r=0,int _v=0):l(_l),r(_r),v(_v) {}
};

vector<Query> Q;

struct Trie {
	struct Tree {
		int child[2],size;
	} tree[maxn*maxb];
	int size;
	int insert(int pre,int v,int depth) {
		int now=++size;
		tree[now]=tree[pre];
		tree[now].size++;
		if(depth<0)return now;
		int x=v>>depth&1;
		tree[now].child[x]=insert(tree[pre].child[x],v,depth-1);
		return now; 
	}
	int ans;
	void query(int depth,int k) {
		int sum=0;
		bool bj=0;
		for(int i=0; i<Q.size(); i++) {
			int x=Q[i].v>>depth&1;
			sum+=tree[tree[Q[i].r].child[x^1]].size-tree[tree[Q[i].l].child[x^1]].size;
		}
		if(sum>=k) {
			ans+=1<<depth;
			bj=1;
		} else k-=sum;
		for(int i=0; i<Q.size(); i++) {
			int x=Q[i].v>>depth&1;
			Q[i].l=tree[Q[i].l].child[x^bj];
			Q[i].r=tree[Q[i].r].child[x^bj];
		}
		if(depth&&k)query(depth-1,k);
	}
} trie;

int n,m,q,a[maxn],b[maxn],root[maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=1; i<=m; i++) {
		b[i]=Get_Int();
		root[i]=trie.insert(root[i-1],b[i],30);
	}
	q=Get_Int();
	for(int i=1; i<=q; i++) {
		int u=Get_Int(),d=Get_Int(),l=Get_Int(),r=Get_Int(),k=Get_Int();
		Q.clear();
		trie.ans=0;
		for(int j=u; j<=d; j++)Q.push_back(Query(root[l-1],root[r],a[j]));
		trie.query(30,k);
		printf("%d\n",trie.ans);
	}
	return 0;
}