单点时限: 3.0 sec
内存限制: 512 MB
现有一个 n×n 的 01 矩阵 M。
定义 cost(i,j) 为：把第 i 行和第 j 列全部变成 1 最少需要改动多少个元素。
定义矩阵的痛苦值 pain(M) 为：
pain(M)=(∑i=1n∑j=1n(cost(i,j))2)mod(109+7)
要求求出初始矩阵的痛苦值和每次修改操作之后的痛苦值。
第一行三个正整数 n,k,q (2≤n≤2⋅105, 1≤k≤min(n2,2⋅105), 0≤q≤2⋅105)。k 表示这个矩阵中有 k 个 1。q 表示修改操作次数。
接下来 k 行，每行两个正整数 xi, yi (1≤xi,yi≤n)，表示有一个 1 在第 xi 行，第 yi 列。保证所有 (xi,yi) 各不相同。
接下来 q 行，每行两个正整数 ui, vi (1≤ui,vi≤n)，表示修改第 ui 行，第 vi 列。如果该位置原先为 0，则改为 1；如果该位置原先为 1，则改为 0。
输出 q+1 行，依次为所有修改发生前的痛苦值，和每次修改操作后的痛苦值。
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
73 48 75 52 29 52 33 52 77 104
(110 001 100)
九个位置的 cost 分别为 2, 3, 2, 2, 3, 4, 3, 3, 3。所以痛苦值是 5×32+3×22+1×42=73。
经过第一次修改后，矩阵变为：
(110 001 101)