#P6466. 分散层叠算法(Fractional Cascading)

分散层叠算法(Fractional Cascading)

题目背景

Fractional Cascading 算法,国内多译为“分散层叠”。

本题仅提供一个简单而经典的方式给算法验证正确性,原则上会尽量卡掉比较暴力的做法,但不保证乱搞一定无法通过。

题目描述

给出 kk 个长度为 nn有序数组

现在有 qq 个查询 : 给出数 xx,分别求出每个数组中大于等于 xx 的最小的数(非严格后继)。

若后继不存在,则定义为 00

每个查询的答案定义为 kk 个后继的异或和

你需要在线地回答这些询问。

由于输出太多不好,给出参数 dd,你只需要输出编号为 dd 的倍数的询问的答案。询问从 11 开始编号。

输入格式

第一行四个整数 n,k,q,dn,k,q,d,意义如题面所述。

kk 行,每行 nn 个整数,描述一个数组。所有数组中出现过的数不重复,保证每个数组严格递增。

qq 行,每行一个整数 xx,描述一个询问。

输入中所得的 xx 需要与上一个询问的答案(无论是否输出)异或解密,如果这是第一个询问,则无需操作。

输出格式

对于编号为 dd 的倍数的每个询问,输出一行一个整数,表示 kk 个后继的异或和。

6 3 8 1
1 4 6 7 10 20 
2 3 8 11 14 18 
5 9 12 13 15 17 
20
6
9
4
29
5
14
9
20
6
9
23
13
11
11
3
2 4 1 1
64 65
25 26
44 62
35 81
81
81
20 4 10 1
553 897 1333 1949 2261 2541 2901 3133 3209 3713 4373 4749 5761 7405 8733 10417 13013 15185 16825 16981 
246 750 806 1534 2274 2470 2486 3278 3954 4618 5306 5638 6114 6310 7106 7522 7734 8170 8702 8974 
1047 1275 2347 2711 3607 4719 5911 6051 7099 7519 8087 8435 8499 8687 8835 10151 10491 11159 11915 12483 
548 1392 2188 3260 3404 3768 5076 5668 5732 6612 7284 7492 8900 9008 9536 9768 11160 12096 12300 13100 
3133
3331
4139
2685
2229
1163
3228
2694
3913
7058
600
8156
676
1176
600
3800
8
432
8156
320

提示

样例解释

对于样例 1,解密后的数据为:

6 3 8 1
1 4 6 7 10 20
2 3 8 11 14 18
5 9 12 13 15 17
20
18
15
13
10
8
5
2

数据规模的与约定

  • 对于 20%20\% 的数据,k10k\leq 10n1000n\leq 1000q1000q\leq 1000
  • 对于 50%50\% 的数据,k10k\leq 10q2×105q\leq 2\times 10^5
  • 对于 100%100\% 的数据,1k1001 \leq k\leq 1002n1042\leq n\leq 10^4q5×105q\leq 5\times 10^51d101\leq d\leq 10,解密后输入中出现的数均在 [1,5×108)[1,5\times 10^8) 范围内。