#P7234. [2023省队模拟]悬念

    ID: 7068 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-无向连通分量基环树拆环换根 DP子树转区间懒标记线段树

[2023省队模拟]悬念

题目描述

有 mm 名女生,编号为 00 到 m−1m-1,和 nn 名男生,编号为 00 到 n−1n-1。保证 m≤nm\le n,且 nn 为奇数。

每名女生都要选择一名男生作为学习伙伴,两名女生不能选择同一名男生。若

min⁡((j−ai) mod n,(ai−j) mod n)=bi,\min((j-a_i)\bmod n,(a_i-j)\bmod n)=b_i,

则第 ii 名女生可选择第 jj 名男生,记这对关系为 (i,j)(i,j)。取模结果在 [0,n)[0,n) 内,例如 −1 mod 3=2-1\bmod3=2。

每对可行关系都有一个愉悦程度。要求在所有女生都找到伙伴的前提下,最大化所选关系的愉悦程度之和。数据保证存在这样的匹配。

接下来有 qq 次修改。每次将编号为 xx 的关系的愉悦程度设为 vv。需要求出最初以及每次修改后最大的愉悦程度之和。修改参数可能用上一次答案加密。

输入格式

第一行三个整数 m,n,Tm,n,T,其中 TT 是加密参数。

第二行 mm 个整数 a0,a1,…,am−1a_0,a_1,\ldots,a_{m-1}。

第三行 mm 个整数 b0,b1,…,bm−1b_0,b_1,\ldots,b_{m-1}。

第四行依次给出每对可行关系的初始愉悦程度。关系按 (i,j)(i,j) 的字典序编号,从 11 开始。

下一行一个整数 qq。接下来 qq 行,每行两个整数 x′,v′x',v'。若上一次答案为 lastans\mathrm{lastans},解密后

$$x=x'-\mathrm{lastans}\cdot T,\qquad v=v'-\mathrm{lastans}\cdot T.$$

保证编号为 xx 的关系存在。

输出格式

输出 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

样例输入 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×1051\le m\le n\le5\times10^5,nn 为奇数,0≤ai<n0\le a_i<n,0≤bi≤⌊n/2⌋0\le b_i\le\lfloor n/2\rfloor,0≤q≤8×1050\le q\le8\times10^5。任何时刻,每对关系的愉悦程度都是 [0,1300][0,1300] 中的整数。

子任务 分值 nn 的限制 qq 的限制 TT 的限制
1 7 1≤n≤91\le n\le9 0≤q≤90\le q\le9 T=0T=0
2 10 1≤n≤181\le n\le18 0≤q≤180\le q\le18
3 17 1≤n≤1001\le n\le100 0≤q≤1000\le q\le100
4 15 1≤n≤50001\le n\le5000 0≤q≤50000\le q\le5000 T∈{0,1}T\in\{0,1\}
5 11 1≤n≤2×1051\le n\le2\times10^5 q=0q=0 T=0T=0
6 13 0≤q≤2×1050\le q\le2\times10^5 T∈{0,1}T\in\{0,1\}
7 12 1≤n≤5×1051\le n\le5\times10^5 0≤q≤5×1050\le q\le5\times10^5 T=0T=0
8 15 T∈{0,1}T\in\{0,1\}