3643. 痛苦的 01 矩阵

单测试点时限: 3.0 秒

内存限制: 512 MB

现有一个 的 01 矩阵

定义 为:把第 行和第 列全部变成 1 最少需要改动多少个元素。

定义矩阵的痛苦值 为:

要求求出初始矩阵的痛苦值和每次修改操作之后的痛苦值。

输入

第一行三个正整数 (, , )。 表示这个矩阵中有 个 1。 表示修改操作次数。

接下来 行,每行两个正整数 , (),表示有一个 1 在第 行,第 列。保证所有 各不相同。

接下来 行,每行两个正整数 , (),表示修改第 行,第 列。如果该位置原先为 0,则改为 1;如果该位置原先为 1,则改为 0。

输出

输出 行,依次为所有修改发生前的痛苦值,和每次修改操作后的痛苦值。

样例

Input
3 4 9
1 1
1 2
2 3
3 1
3 3
1 2
1 3
2 2
2 2
2 1
3 1
1 1
2 3
Output
73
48
75
52
29
52
33
52
77
104

提示

九个位置的 分别为 2, 3, 2, 2, 3, 4, 3, 3, 3。所以痛苦值是

经过第一次修改后,矩阵变为:

56 人解决,80 已尝试。

87 份提交通过,共有 476 份提交。

7.5 EMB 奖励。

创建: 7 月前.

修改: 2 月,1 周前.

最后提交: 2 天,16 小时前.

来源: EOJ Monthly 2018.10

标签