BZOJ

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.