PROBLEM LINK:
Author: Abhinav Jain
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
SIMPLE
PREREQUISITES:
Math
PROBLEM:
Given an N\times M matrix filled with zeroes initially, and Q operations. Each operation (X_i, Y_i) means to add 1 to the row x and also to the column y. (Note that 1 is added twice to the cell (X_i, Y_i).) The task is to compute the number of cells with odd values after all Q operations.
QUICK EXPLANATION:
Rows and columns are independent. Suppose there are r rows added an odd number of times, and c columns added an odd number of times. Then the answer is rM+cN-2rc.
EXPLANATION:
Subtask 1
Since T,N,M,Q\le 300 in this subtask, a straightforward solution with complexity O(T((N+M)Q+NM)) can pass. We simply implement every query, and each query takes O(N+M) time. After then we use O(NM) time to count the number of odd cells.
Subtask 2
In this subtask, N\cdot M\le 10^6 and Q\le 10^6. For each row x (1\le x\le N), let A[x] be the number of operations on it. Then A[x] is simply the number of i's such that X_i=x. For each column y (1\le y\le M), let B[y] be the number of operations on it, thus similarly B[y] is the number of i's such that Y_i=y. We can compute A[x] and B[y] by the following pseudocode:
Initially A[x]=B[y]=0 for every x, y;
for i = 1 to Q
A[X[i]] += 1
B[Y[i]] += 1
The value at cell (x,y) is simply A[x]+B[y], since it’s added by this many operations. We can iterate through the matrix to find the number of odd cells:
ans = 0
for x = 1 to N
for y = 1 to M
val = A[x] + B[y]
if val % 2 == 1 then ans += 1
This takes O(Q+MN) time per test case.
Subtask 3
Actually, we don’t need to spend O(MN) time to count the number of odd cells. Suppose there are r rows operated an odd number of times (i.e. A[x] is odd, where x is the row index). Suppose there are c columns operated an odd number of times (i.e. B[y] is odd, where y is the column index). Then the answer is r\cdot M+c\cdot N-2r\cdot c.
Proof
Consider the following diagram, where the first r rows and first c columns are operated an odd number of times. Let’s count the number of odd cells row by row.
- In the i_1-th row where i_1\le r, the cells not in the first c columns are odd. (Because if you don’t do column operations at all, every number is odd. If you did an odd number of column operations, the corresponding cell becomes even.) There are r such rows, each row has (M-c) odd cells.
- In the i_2-th row where i_2>r, the cells in the first c columns are odd. There are N-r such rows, each row has c odd cells.
Therefore, there are r(M-c)+c(N-r)=r\cdot M+c\cdot N-2r\cdot c odd cells.
Alternatively, the odd cells are exactly those in the shaded area. It’s also easy to see that there are r(M-c)+c(N-r) odd cells.
The time complexity is, therefore, O(M+N+Q).
ALTERNATE EXPLANATION:
Please feel free to share your approach 
SOLUTIONS:
Setter's Solution
// Author : Abhinav Jain
// Institution: Jaypee Institute of information Technology
// AC COde
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define cases int testcases;cin>>testcases; while(testcases--)
int Row[100005],Col[100005];
int32_t main()
{
cases
{
int n,m,q,x,y;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
Row[i]=0;
}
for(int i=1;i<=m;i++)
{
Col[i]=0;
}
/*n=3 m=4
00 01 02 03
10 11 12 13
20 21 22 23
*/
while(q--)
{
cin>>x>>y;
Row[x]++;
Col[y]++;
Row[x]%=2;Col[y]%=2;
}
int a=0,b=0,c=0,d=0;
for(int i=1;i<=n;i++)
{
if(Row[i]==1) a++;
else b++;
}
for(int i=1;i<=m;i++)
{
if(Col[i]==1)c++;else d++;
}
int res= (a*d + b*c);
cout<<res<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
void pi(ll x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}
int n, m, q, row[100200], col[100200];
void doit() {
int i, j, r, c;
gi(n); gi(m); gi(q);
for (i = 1; i <= n; i++) row[i] = 0;
for (j = 1; j <= m; j++) col[j] = 0;
while (q--) {
gi(i); gi(j);
row[i] ^= 1; col[j] ^= 1;
}
for (i = 1, r = 0; i <= n; i++) if (row[i]) r++;
for (j = 1, c = 0; j <= m; j++) if (col[j]) c++;
pi(1ll * r * m + 1ll * n * c - 2ll * r * c); putchar('\n');
}
int main() {int t; gi(t); while (t--) doit(); return 0;}
