3643. 痛苦的 01 矩阵

单点时限: 3.0 sec

内存限制: 512 MB

现有一个 $n \times n$ 的 01 矩阵 $\boldsymbol M$。

定义 $cost(i,j)$ 为:把第 $i$ 行和第 $j$ 列全部变成 1 最少需要改动多少个元素。

定义矩阵的痛苦值 $pain(\boldsymbol M)$ 为:

$$pain(\boldsymbol M) = \left( \sum_{i=1}^n \sum_{j=1}^n \left( cost(i,j) \right)^2 \right) \bmod (10^9+7)$$

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

输入格式

第一行三个正整数 $n, k, q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le \min(n^2, 2 \cdot 10^5)$, $0 \le q \le 2 \cdot 10^5$)。$k$ 表示这个矩阵中有 $k$ 个 1。$q$ 表示修改操作次数。

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

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

输出格式

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

样例

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

提示

$$
\begin{pmatrix}
1 & 1 & 0 \
0 & 0 & 1 \
1 & 0 & 0
\end{pmatrix}
$$

九个位置的 $cost$ 分别为 2, 3, 2, 2, 3, 4, 3, 3, 3。所以痛苦值是 $5 \times 3^2 + 3 \times 2^2 + 1 \times 4^2 = 73$。

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

$$
\begin{pmatrix}
1 & 1 & 0 \
0 & 0 & 1 \
1 & 0 & 1
\end{pmatrix}
$$

62 人解决,90 人已尝试。

93 份提交通过,共有 523 份提交。

4.5 EMB 奖励。

创建: 2 年,4 月前.

修改: 1 年,12 月前.

最后提交: 3 周,4 天前.

来源: EOJ Monthly 2018.10

题目标签