题目描述
有 m 名女生,编号为 0 到 m−1,和 n 名男生,编号为 0 到 n−1。保证 m≤n,且 n 为奇数。
每名女生都要选择一名男生作为学习伙伴,两名女生不能选择同一名男生。若
min((j−ai)modn,(ai−j)modn)=bi,
则第 i 名女生可选择第 j 名男生,记这对关系为 (i,j)。取模结果在 [0,n) 内,例如 −1mod3=2。
每对可行关系都有一个愉悦程度。要求在所有女生都找到伙伴的前提下,最大化所选关系的愉悦程度之和。数据保证存在这样的匹配。
接下来有 q 次修改。每次将编号为 x 的关系的愉悦程度设为 v。需要求出最初以及每次修改后最大的愉悦程度之和。修改参数可能用上一次答案加密。
输入格式
第一行三个整数 m,n,T,其中 T 是加密参数。
第二行 m 个整数 a0,a1,…,am−1。
第三行 m 个整数 b0,b1,…,bm−1。
第四行依次给出每对可行关系的初始愉悦程度。关系按 (i,j) 的字典序编号,从 1 开始。
下一行一个整数 q。接下来 q 行,每行两个整数 x′,v′。若上一次答案为 lastans,解密后
$$x=x'-\mathrm{lastans}\cdot T,\qquad v=v'-\mathrm{lastans}\cdot T.$$
保证编号为 x 的关系存在。
输出格式
输出 q+1 行,每行一个整数,依次为初始状态及每次修改后的答案。
样例输入 1
8 9 0
5 6 2 0 1 5 7 3
4 4 1 4 4 1 0 4
3 2 4 1 0 0 2 0 3 2 5 4 2 3 1
9
3 0
2 4
3 6
6 6
5 12
11 8
13 4
14 9
15 0
样例输出 1
19
16
17
21
27
28
29
31
31
30
样例输入 2
6 9 1
5 1 2 0 1 3
4 0 0 4 4 4
13 19 17 6 4 16 0 4 13 8
9
75 70
60 70
55 59
59 65
69 74
79 70
70 77
69 72
73 77
样例输出 2
69
57
53
53
61
70
65
65
66
66
数据范围与约定
对于全部数据,1≤m≤n≤5×105,n 为奇数,0≤ai<n,0≤bi≤⌊n/2⌋,0≤q≤8×105。任何时刻,每对关系的愉悦程度都是 [0,1300] 中的整数。
| 子任务 |
分值 |
n 的限制 |
q 的限制 |
T 的限制 |
| 1 |
7 |
1≤n≤9 |
0≤q≤9 |
T=0 |
| 2 |
10 |
1≤n≤18 |
0≤q≤18 |
| 3 |
17 |
1≤n≤100 |
0≤q≤100 |
| 4 |
15 |
1≤n≤5000 |
0≤q≤5000 |
T∈{0,1} |
| 5 |
11 |
1≤n≤2×105 |
q=0 |
T=0 |
| 6 |
13 |
0≤q≤2×105 |
T∈{0,1} |
| 7 |
12 |
1≤n≤5×105 |
0≤q≤5×105 |
T=0 |
| 8 |
15 |
T∈{0,1} |