Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

05/20
18:44
可持久化trie

[bzoj 4103] [Thu Summer Camp 2015]异或运算

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym},令矩阵A中第i行第j列的值Aij=xi xor  yj,每次询问给定矩形区域i∈[u,d],j∈[l,r],找出第k大的Aij。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含两个正整数n,m,分别表示两个数列的长度

第二行包含n个非负整数xi
第三行包含m个非负整数yj
第四行包含一个正整数p,表示询问次数
随后p行,每行均包含5个正整数,用来描述一次询问,每行包含五个正整数u,d,l,r,k,含义如题意所述。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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   ♦♦♦♦♦♦

6
5
1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据,0<=Xi,Yj<2^31,

1<=u<=d<=n<=1000,
1<=l<=r<=m<=300000,
1<=k<=(d-u+1)*(r-l+1),
1<=p<=500

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

对m个数建立可持久化trie

对于每个询问,对u-d中的所有数记录下当前匹配到哪个节点,然后依次计算答案即可

 

[bzoj 4103] [Thu Summer Camp 2015]异或运算