BZOJ 4103

不稳定的传送门

Description

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

Input

第一行包含两个正整数$n,m$,分别表示两个数列的长度
第二行包含$n$个非负整数$x_i$
第三行包含$m$个非负整数$y_j$
第四行包含一个正整数$p$,表示询问次数
随后$p$行,每行均包含$5$个正整数,用来描述一次询问,每行包含五个正整数$u,d,l,r,k$,含义如题意所述。

Output

共$p$行,每行包含一个非负整数,表示此次询问的答案。

Sample Input

1
2
3
4
5
6
7
3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4

Sample Output

1
2
3
6
5
1

Hint

对于$100\%$的数据,$0<=X_i,Y_j<2^{31}$,
$1\leq u\leq d\leq n\leq 1000$,
$1\leq l\leq r\leq m\leq 300000$,
$1\leq k\leq (d-u+1)*(r-l+1)$,
$1\leq p\leq 500$

按照$m$这一维度建可持久化Trie

每个询问中的每个$n$维度的点单独决定是走$1$还是走$0$,找第$k$大的方法直接仿照找别的树第$k$大那样就行了

刚开始总想把$n$维度的点都合在一起找,后来发现不行的说


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
program bzoj_4103;
const log=31;
var s:array[0..9900000]of record son:array[0..1]of longint; size:longint; end;
root:array[0..300000]of longint;
n,m,i,j,tot,p,b,x1,y1,x2,y2,k,len:longint;
a:array[1..1000]of longint;
seq:array[1..1000]of record l,r,k:longint; end;
procedure insert(var t:longint;st,pos,base:longint);
var x:longint;
begin
inc(tot);
t:=tot;
s[t]:=s[base];
inc(s[t].size);
if pos<0 then exit;
x:=st>>pos and 1;
insert(s[t].son[x],st,pos-1,s[base].son[x]);
end;
function query(pos,k:longint):longint;
var i,x,cnt,t:longint;
begin
if pos<0 then exit(0);
cnt:=0;
for i:=1 to len do
begin
x:=(seq[i].k>>pos and 1)xor 1;
inc(cnt,s[s[seq[i].r].son[x]].size-s[s[seq[i].l].son[x]].size);
end;
t:=ord(k<=cnt);
for i:=1 to len do
begin
x:=(seq[i].k>>pos and 1)xor t;
seq[i].l:=s[seq[i].l].son[x];
seq[i].r:=s[seq[i].r].son[x];
end;
exit(t<<pos or query(pos-1,k-(t xor 1)*cnt));
end;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
tot:=0;
root[0]:=0;
s[0].son[0]:=0;
s[0].son[1]:=0;
s[0].size:=0;
for i:=1 to m do
begin
read(b);
insert(root[i],b,log,root[i-1]);
end;
readln(p);
for i:=1 to p do
begin
readln(x1,x2,y1,y2,k);
len:=x2-x1+1;
for j:=x1 to x2 do with seq[j-x1+1] do
begin
l:=root[y1-1];
r:=root[y2];
k:=a[j];
end;
writeln(query(log,k));
end;
end.