UOJ Logo Universal Online Judge

UOJ

#682. 【UR #22】月球铁轨

附件下载 统计

伏特再次找到了工程师,请他们设计铁轨。工程师很快给出了一张模板图纸作为候选方案。

图纸上 $n$ 段铁轨排成一行,依次编号为 $1, \dots, n$。根据工程师们的设计,第 $i$ 段铁轨的尾部只能和第 $i+1$ 段铁轨的头部相连 $(1\leq i < n)$,否则铁轨会变的极为不稳定。

伏特不必铺设所有的铁轨。伏特可以选择一个编号区间,如 $[l, r]$,然后下令只铺设编号在区间 $[l, r]$ 中的铁轨。显然区间的选择方案一共只有 $\frac{n(n+1)}{2}$ 种。

跳蚤国拥有独特的材料科学,每段铁轨都可以使用两种材料中的一种构建,稳定度分别为 $a_i,b_i$,且不同段铁轨可以使用不同材料。根据工程师们的建模,对于一个区间选择方案 $[l, r]$,如果第 $i$ 段铁轨选择了稳定度为 $p_i$ 的材料 ($p_i \in \{a_i, b_i\}$),那么铺设区间 $[l, r]$ 中的所有铁轨的总稳定度为该区间内所有 $p_i$ 的异或和,即 $p_l \oplus p_{l+1} \oplus \cdots \oplus p_r$,其中 $\oplus$ 表示异或。

对于每个区间 $[l, r]$,工程师早已算好了在所有可能的材料选择方案中总稳定度的最大值,称之为该区间的最优稳定度

现在伏特找到了你,希望你能帮工程师们验算一番。请你求出所有可能的区间中,第 $k$ 小的最优稳定度是多少。

输入格式

第一行两个整数 $n, k$,表示铁轨段数和要求的最优稳定度排名。

第二行 $n$ 个整数,第 $i$ 个整数为 $a_i$,表示使用材料一修建的稳定度。

第三行 $n$ 个整数,第 $i$ 个整数为 $b_i$,表示使用材料二修建的稳定度。

输出格式

一行一个整数表示第 $k$ 小的最优稳定度。

样例一

input

3 3
1 2 3
4 5 6

output

6

explanation

六种区间选择方案对应的最优稳定度分别为

  • 区间 $[1,1]$: 最优稳定度为 $4$;
  • 区间 $[1,2]$: 最优稳定度为 $6$;
  • 区间 $[1,3]$: 最优稳定度为 $7$;
  • 区间 $[2,2]$: 最优稳定度为 $5$;
  • 区间 $[2,3]$: 最优稳定度为 $6$;
  • 区间 $[3,3]$: 最优稳定度为 $6$.

样例二

input

10 1
3 30 30 20 10 4 24 0 17 16
3 3 14 19 26 28 13 13 2 27

output

3

样例三、四、五、六

见附件下载。

样例四,五分别满足特殊性质 A,B

限制与约定

对于 $100\%$ 的数据,$1\leq n\leq 10^5,1\leq m \leq 30,0\leq a_i,b_i\lt 2^m,1\leq k\leq \frac{n(n+1)}{2}$,其中 $m$ 是用于限定值域的参数。

子任务编号 $n\leq$ $m=$ 特殊性质 分值
1 $10^3$ $20$ $10$
2 $3\times 10^4$ $15$
3 $10^5$ $30$ A $15$
4 B $15$
5 C $15$
6 $30$

特殊性质说明:

  • A: $a_i,b_i$ ($1\leq i\leq n$) 均在 $[0,2^m)$ 范围内独立等概率随机。
  • B: $a_i=b_i$ ($1\leq i\leq n$)。
  • C: $a_i=0$ ($1\leq i\leq n$)。

时间限制:$\texttt{4s}$

空间限制:$\texttt{512MB}$