### PROBLEM LINK

### Panel Members

**Problem Setter:** Amit Pandey

**Problem Tester:** Pushkar Mishra

**Editorialist:** Prateek Gupta

**Contest Admin:** Praveen Dhinwa and Pushkar Mishra

**Russian Translator:** Sergey Kulik

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Basic Programming, Logic

### PROBLEM:

Given a binary matrix having 1s and 0s. Each i^{th}row of the matrix contains 1s only in the given contiguous range [l[i], r[i]]. For each query, you need to find the sum of the matrix modulo 2 if some given x^{th} row and y^{th} column are supposedly removed from the matrix. Also, each query does not modify the state of the matrix after its been processed.

### EXPLANATION:

Let initialSum be the sum of the original matrix.

Let rowSum[i] and colSum[i] denote the sum of the elements of i^{th} row and column respectively in the original matrix.

Let A[i][j] denote the value at cell (i,j) formed by intersection of i^{th} row and i^{th} column.

For each query, the sum of the final matrix for each query(x,y) will be equal to initialSum - rowSum[x] - colSum[y] + A[x][y]

initialSum of the matrix can be calculated as summation of r[i] - l[i] + 1 for each i \mathcal\in [1,N].

rowSum[x] is already the number of ones in the i^{th} row i.e r[x] - l[x] + 1.

A[x][y] is 1 if and only if j \mathcal\in [l[x],r[x]].

Only task now left is to calculate colSum[y].

**Solution for Subtask 1:**

To calculate the value of colSum[y], we need to find out how many rows have y \mathcal\in [l[i],r[i]] for each i from [1,N].

For this, we can iterate each row and find out. This approach will take \mathcal{O}(N) per query which is infact slow for Subtask 2 to pass.

**Solution for Subtask 2:**

We can calculate the values of colSum[y] before hand for all y \mathcal\in [1,N]. For each rowSum[i], we basically have to increase colSum[j] += 1 where j \mathcal\in [l[i],r[i]].

In other words, we can do a range update in the following manner :-

```
for ( int i = 1; i <= N; i++ ) colSum[l[i]]++, colSum[r[i]+1]--;
```

We can then do a cumulative sum to compute individual values for each column.

```
for ( int i = 1; i <= N; i++ ) colSum[i] += colSum[i-1];
```

How do above range updates work?

When you have to increase a particular range[i,j] in the empty array with 1, you increase A[i] += 1, meaning you have increased all the numbers from i uptill infinity to 1. That’s because when you take the cumulative sum after doing the update at position i, you see all values having index than or equal to i are now 1. But, in your case ,you want them to be increased uptill index j only. Hence, to counter balance the effect caused, you do A[j+1] -= 1 and then take the cumulative sum. If you see now, all the values in range$[i,j]$ are increased to 1 while rest of them remain 1.

We now have all the necessary parameters that we need to answer each query in a constant number of operations.

### COMPLEXITY

Overall Complexity for the solution to pass all the subtasks is \mathcal{O}(N) precomputation and then \mathcal{O}(1) per query. For details on the implementation, please have a look at the solutions below.