#523. 「LibreOJ β Round #3」绯色 IOI(悬念)

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

考场的炸弹危机被成功解决了,元凶被绳之以法,IOI 顺利进行。Jsp 和 Rlc 利用最后的半小时 AK 了所有题并取得了前两名。

今天是一个活动的日子,一向沉默的 Jsp 突然向 Rlc 提出了一个游戏。

「怎么了,Jsp?」
「……」
「……」
「上次的问题,你的答案又是什么呢?」

Jsp 和 Rlc 的人格魅力吸引了世界各国的 IOI 选手来玩(*)游(*)戏(*)。这其中有 mm 个妹子跟着 Rlc,编号为 0,1,...,m10,1,...,m-1;有 nn 个男生跟着 Jsp,编号为 0,1,...,n10,1,...,n-1。由于某些原因,总有 mnm\leq n,且 nn 是奇数。

现在 Rlc 准备让每个妹子选一个男生(当然,不包括 Jsp)作为同伴,一起学习 Chinese Data Structure。两个妹子不能选择同一个男生

当然,由于语言障碍等原因妹子不是和所有男生都能愉快交流的。第 ii 个妹子能选择的男生可以由两个数 aia_ibib_i 来描述:

对于 00m1m-1 中的每个 ii00n1n-1 中的每个 jj,若 jj 满足 min((jai)modn,(aij)modn)=bi\min((j-a_i)\bmod n,(a_i-j)\bmod n)=b_i(注意这里取模的值域是 [0,n)[0,n),如 1mod3=2-1 \bmod 3 = 2),则第 ii 个妹子和第 jj 个男生可以交流,称这对关系为 (i,j)(i,j)

Rlc 发现自己这边的妹子可以做到人人有同伴。但仅仅做到这一点是不行的,妹子和男生学习过程中的愉悦程度因人而异,Rlc 希望愉悦程度的总和最大。

不过某两人之间的愉悦程度有时会发生变化,这种变化一共有 qq 次。Rlc 用两个整数 x,vx,v 来描述变化,表示第 xx 对关系的愉悦程度变为 vv

Jsp 需要在一开始以及每次操作后回答:在所有妹子都有自己同伴的前提下,每一对同伴的愉悦程度的总和最大是多少。

有时为了强制 Jsp 按顺序回答,Rlc 会用上一次的答案加密自己对愉悦程度变化的描述。


一句话题意:在线动态维护一个二分图的最大权最大匹配。保证左侧满匹配。

输入格式

第一行三个整数 m,n,Tm,n,T。其中 TT 表示加密参数。
接下来一行 mm 个整数 a0,a1,...,am1a_0,a_1,...,a_{m-1}
接下来一行 mm 个整数 b0,b1,...,bm1b_0,b_1,...,b_{m-1}
接下来一行若干个整数 vv,按编号从小到大依次表示每对关系的初始愉悦程度。
接下来一行一个整数 qq
接下来 qq 行每行两个整数 x,vx',v',表示加密后的描述。
解密方法是:设上次答案为 lastans\text{lastans},则真实的 x=xlastansT,v=vlastansTx=x'-\text{lastans}\cdot T,v=v'-\text{lastans}\cdot T。保证这个关系存在。

每对关系 (i,j)(i,j) 按照iijj 的顺序编号。即:

//no[i][j] 表示关系 (i,j) 的编号。

cnt = 0

for i = 0 to m - 1 do
    for j = 0 to n - 1 do
        if min((j - a[i]) mod n,(a[i] - j) mod n) = b[i] then
            no[i][j] := ++ cnt
        end if
    end for
end for

输出格式

输出共 q+1q+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

样例解释 1

样例中描述的二分图如下:

1.png

样例输入 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

数据范围与提示

对于所有数据,1mn5×105,n1\leq m\leq n\leq 5\times 10^5,n 是奇数 ,0ai<n,0bin2,0q8×105,0\leq a_i< n,0\leq b_i\leq \lfloor \frac{n}{2}\rfloor,0\leq q\leq 8\times 10^5,任何时刻每对关系的愉悦程度是 [0,1300][0,1300] 中的整数。

数据保证存在一个匹配使得每个妹子都能找到自己的伙伴。

Subtask # 分值 m,nm,n 的限制 qq 的限制 TT 的限制
1 77 1n91\leq n\leq 9 0q90\leq q\leq 9 T=0T=0
2 1010 1n181\leq n\leq 18 0q180\leq q\leq 18 T=0T=0
3 1717 1n1001\leq n\leq 100 0q1000\leq q\leq 100 T=0T=0
4 1515 1n50001\leq n\leq 5000 0q50000\leq q\leq 5000 T{0,1}T\in\{0,1\}
5 1111 1n2×1051\leq n\leq 2\times 10^5 q=0q=0 T=0T=0
6 1313 1n2×1051\leq n\leq 2\times 10^5 0q2×1050\leq q\leq 2\times 10^5 T{0,1}T\in\{0,1\}
7 1212 1n5×1051\leq n\leq 5\times 10^5 0q5×1050\leq q\leq 5\times 10^5 T=0T=0
8 1515 1n5×1051\leq n\leq 5\times 10^5 0q5×1050\leq q\leq 5\times 10^5 T{0,1}T\in\{0,1\}