Difficulty: Very Easy

Importance: ★ ★ ★

Prefix Sum

1D Prefix Sum

Given an array of $n$ integers $a_1,a_2,\ldots,a_n$, the prefix sum array $\text{pre}$ is defined as:

\[\text{pre}_i = \sum_{j = 1}^ia_j, \quad \forall \; 1 \le i \le n\]

That is, $\text{pre}_i$ stores the sum of the first $i$ elements of the array.

This array can be computed iteratively in $O(n)$ time using the following relations:

\[\begin{aligned} & \text{pre}_0 = 0 \\[6pt] & \text{pre}_i = \text{pre}_{i-1} + a_i, \quad \forall \; 1 \le i \le n \end{aligned}\]

The most common application of this array is computing the sum of elements in a subarray $[l,r]$ of the array $a$ in $O(1)$ time using the fact:

\[\sum_{j=l}^ra_j \\[6pt] = \sum_{j=1}^ra_j - \sum_{j=1}^{l-1}a_j \\[6pt] = \text{pre}_r - \text{pre}_{l-1}\]

Learn Through Problems

CSES - Static Range Sum Queries

You are given $n$ integers $a_1,a_2,\ldots,a_n$ and $q$ queries of the form: compute the sum of values in range $[l_i,r_i]$.

Input
The first line contains integers $n \left(1 \le n \le 2\cdot10^5\right)$ and $q \left(1 \le q \le 2\cdot10^5\right)$.
The next line contains $n$ integers $a_1,a_2,\ldots,a_n \left(1 \le a_i \le 10^9\right)$.
The next $q$ lines contain integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le n)$.

Output
For each query, print the sum of values in range $[l_i,r_i]$.

Sample Input

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Sample Output

Solution

Build the prefix sum array $\text{pre}$ of the array $a$. The sum of values in range $[l_i,r_i]$ is given by $\text{pre}_{r_i} - \text{pre}_{l_i-1}.$

Time Complexity: $O(n)$

Code (C++)

CSES - Subarray Sums II

You are given $n$ integers $a_1,a_2,\ldots,a_n$ and an integer $x$

Count the number of subarrays of $a$ having sum $x$.

Input
The first line contains integers $n \left(1 \le n \le 2\cdot10^5\right)$ and $x \left(-10^9 \le x \le 10^9\right)$.
The next line contains $n$ integers $a_1,a_2,\ldots,a_n \left(-10^9 \le a_i \le 10^9\right)$.

Output
Print the required number of subarrays.

Sample Input

5 7
2 -1 3 5 -2

Sample Output

Solution

Formally, we have to count the number of pairs $(l,r)$ such that:

$1 \le l \le r \le n$
$\displaystyle \sum_{i = l}^ra_i = x$

Build the prefix sum array $\text{pre}$ of the array $a$. Now the second condition can be written as: $$ \begin{aligned} & \text{pre}_r-\text{pre}_{l-1}=x \\[6pt] \Rightarrow &\; \text{pre}_{l-1} = \text{pre}_r-x \end{aligned} $$ Replacing $l \rightarrow l+1$, we can rewrite both the conditions as:

$0 \le l < r \le n$
$\text{pre}_l = \text{pre}_r-x$

To count the number of pairs $(l,r)$ satisfying this, we can iterate on $r$ from $1$ to $n$ and keep track of the frequencies of $\text{pre}_l$ for $0 \le l < r$.

Time Complexity: $O(n\log n)$

Code (C++)

CSES - Maximum Subarray Sum

You are given $n$ integers $a_1,a_2,\ldots,a_n$.

Find the maximum sum of values in a contiguous non-empty subarray of $a$.

Input
The first line contains integer $n \left(1 \le n \le 2\cdot10^5\right)$.
The next line contains $n$ integers $a_1,a_2,\ldots,a_n \left(-10^9 \le a_i \le 10^9\right)$.

Output
Print the maximum subarray sum.

Sample Input

8
-1 3 -2 5 3 -5 2 2

Sample Output

Solution

Build the prefix sum array $\text{pre}$ of the array $a$. Formally, we have to compute the value of the expression: $$ \begin{aligned} & \max_{1 \le l \le r \le n} \; \sum_{i=l}^{r} a_i \\[6pt] = &\; \max_{1 \le l \le r \le n} \left( \text{pre}_r - \text{pre}_{l-1} \right) \\[6pt] = &\; \max_{1 \le r \le n} \left( \text{pre}_r - \min_{1 \le l \le r} \text{pre}_{l-1} \right) \\[6pt] = &\; \max_{1 \le r \le n} \left( \text{pre}_r - \min_{0 \le l < r} \text{pre}_{l} \right) \end{aligned} $$ To compute this, we can iterate on $r$ from $1$ to $n$ and keep track of $\displaystyle \min_{0 \le l < r} \text{pre}_{l}$.

Time Complexity: $O(n)$

Code (C++)

Codeforces - Array Splitting

You are given $n$ integers $a_1,a_2,\ldots,a_n$ and an integer $k$.

Divide the array $a$ into $k$ non-empty consecutive subarrays. The subarrays are indexed from left to right as $1,2,\ldots,k$. The cost of the division is given as: $$\sum_{i = 1}^n\left(a_i \cdot f(i)\right)$$ where $f(i)$ is the index of the subarray containing $a_i$.

Find the maximum cost that can be obtained by dividing the array $a$ into $k$ non-empty consecutive subarrays.

Input
The first line contains integers $n$ and $k \left(1 \le k \le n \le 3\cdot10^5\right)$.
The next line contains integers $a_1,a_2,\ldots,a_n \left(-10^6 \le a_i \le 10^6\right)$.

Output
Print the maximum cost that can be obtained by dividing the array $a$ into $k$ non-empty consecutive subarrays.

Sample Input

5 2
-1 -2 5 -4 8

Sample Output

Solution

Let the array $a$ be divided into $k$ subarrays as $[i_0+1,i_1],[i_1+1,i_2],\ldots,[i_{k-1}+1,i_k]$, where $i_0 = 0 < i_1 < i_2 < \ldots < i_{k-1} < i_k = n$.

Build the prefix sum array $\text{pre}$ of the array $a$. We can rewrite the cost of the division as: $$ \begin{aligned} & \sum_{l = 1}^k\sum_{r = i_{l - 1} + 1}^{i_l}\left(a_r \cdot l\right) \\ =&\; \sum_{l = 1}^kl\cdot\sum_{r = i_{l - 1} + 1}^{i_l}a_r \\ =&\; \sum_{l = 1}^kl\cdot\left(\text{pre}_{i_l} - \text{pre}_{i_{l - 1}}\right) \\ =&\; \sum_{l = 1}^kl\cdot\text{pre}_{i_l}-\sum_{l = 1}^kl\cdot\text{pre}_{i_{l-1}} \\ =&\; \sum_{l = 1}^kl\cdot\text{pre}_{i_l}-\sum_{l = 0}^{k-1}\left(l+1\right)\cdot\text{pre}_{i_{l}} \\ =&\; \sum_{l = 1}^kl\cdot\text{pre}_{i_l}-\sum_{l = 0}^{k-1}l\cdot\text{pre}_{i_{l}}-\sum_{l = 0}^{k-1}\text{pre}_{i_{l}} \\ =&\; k\cdot\text{pre}_{i_k}-\sum_{l = 0}^{k-1}\text{pre}_{i_{l}} \\ =&\; k\cdot\text{pre}_{n}-\sum_{l = 1}^{k-1}\text{pre}_{i_{l}} \left(\because i_k = n,\text{pre}_{i_0} = \text{pre}_0 = 0\right) \end{aligned} $$ Formally, we have to compute the value of the expression: $$ \begin{aligned} & \max \left(k\cdot\text{pre}_{n}-\sum_{l = 1}^{k-1}\text{pre}_{i_{l}}\right) \\ =&\; k\cdot\text{pre}_{n}-\min\sum_{l = 1}^{k-1}\text{pre}_{i_{l}} \end{aligned} $$ To compute $\displaystyle \min\sum_{l = 1}^{k-1}\text{pre}_{i_{l}}$, we can take the $k-1$ smallest elements from $\left(\text{pre}_1, \text{pre}_2, \ldots, \text{pre}_{n-1}\right)$ since $0 < i_1 < i_2 < \ldots < i_{k-1} < n$.

Time Complexity: $O(n\log n)$

Code (C++)

Codeforces - Karen and Coffee

You are given $n$ intervals $[l_i,r_i]$, where each interval denotes a range of integer temperatures.

A temperature is called admissible if it belongs to at least $k$ of the given intervals.

You are also given $q$ queries. In each query, two integers $a$ and $b$ are given, and you have to determine the number of admissible integer temperatures in the range $[a,b]$.

Input
The first line contains integers $n$, $k \left(1 \le k \le n \le 2\cdot10^5\right)$ and $q \left(1 \le q \le 2\cdot10^5\right)$.
The next $n$ lines contain integers $l_i$ and $r_i \left(1 \le l_i \le r_i \le 2\cdot10^5\right)$.
The next $q$ lines contain integers $a$ and $b \left(1 \le a \le b \le 2\cdot10^5\right)$.

Output
For each query, print the number of admissible integer temperatures in the range $[a,b]$.

Sample Input

Sample Output

Solution

Let us define:

$\displaystyle \text{freq}_i = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j}}^n1$: the number of intervals to which the temperature $i$ belongs, $\quad \forall \; 1 \le i \le N$ where $N = 2\cdot 10^5$.

To efficiently build the $\text{freq}$ array, we use the technique of Difference Array:

Initialize with all zeros.
For every interval $[l_i,r_i]$, we update:
- $\text{freq}_{l_i} \gets \text{freq}_{l_i}+1$
- $\text{freq}_{r_i+1} \gets \text{freq}_{r_i+1}-1$
After processing all the intervals, replace the $\text{freq}$ array with its prefix sum array.

The logic behind this technique is explained below:

When we update $\text{freq}_{l_i} \gets \text{freq}_{l_i}+1$ and later replace the $\text{freq}$ array by its prefix sum array, the frequency of all temperatures $\ge l_i$ gets increased by $1$.
However, for an interval $[l_i,r_i]$, we want to increase the frequency only for temperatures lying in the range $[l_i,r_i]$.
To stop this increment after $r_i$, we update $\text{freq}_{r_i+1} \gets \text{freq}_{r_i+1}-1$ and later replacing the $\text{freq}$ array by its prefix sum cancels the earlier increment for all temperatures $\ge r_i+1$.
As a result, the net effect is that only temperatures in the range $[l_i,r_i]$ have their frequency increased by $1$, while other temperatures remain unaffected.

Let us define: $$ c_i = \begin{cases} 1, & \text{if } \text{freq}_i \ge k \\ 0, & \text{otherwise} \end{cases} ,\quad \forall \;1 \le i \le N. $$ Build the prefix sum array $\text{pre}$ of the array $c$. The number of admissible integer temperatures in the range $[a,b]$ is given by $\text{pre}_b - \text{pre}_{a-1}$.

Time Complexity: $O(N + n + q)$

Code (C++)

CodeChef - Angry Cyborg

There are $n$ cities numbered from $1$ to $n$, in a row from left to right.

The process lasts for $q$ days. On the $j^{th}$ day, two integers $l_j$ and $r_j$ are chosen $\left(1 \le l_j \le r_j \le n\right)$, and the following events occur:

In city $l_j$, $1$ statue is destroyed.
In city $l_j+1$, $2$ statues are destroyed.
$\ldots$
In city $r_j$, $r_j-l_j+1$ statues are destroyed.

Formally, for each $i$ such that $l_j \le i \le r_j$, the number of statues destroyed in city $i$ is $i-l_j+1$.

After $q$ days, determine the total number of statues destroyed in each city.

Input
The first line contains an integer $t \left(1 \le t \le 10^3\right)$.
The first line of each test case contains integers $n \left(1 \le n \le 10^5\right)$ and $q \left(1 \le q \le 10^5\right)$.
The next $q$ lines of each test case contain integers $l_j$ and $r_j \left(1 \le l_j \le r_j \le n\right)$.

Additionally, the following holds true:

The sum of $n$ over all test cases doesn't exceed $10^6$.
The sum of $q$ over all test cases doesn't exceed $10^6$.

Output
For each test case, print $n$ integers, where the $i^{th}$ integer represents the total number of statues destroyed in city $i$ after $q$ days.

Sample Input

Sample Output

2 4 3 1 2
1 0

Solution

Let us define:

$\displaystyle \text{val}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} (i - l_j + 1)$: the total number of statues destroyed in city $i$ after $q$ days, $\quad \forall \; 1 \le i \le n$.

We can rewrite the expression for $\text{val}_i$ as: $$ \begin{aligned} & \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} (i+1) - \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} l_j \\[6pt] =\; & (i+1)\cdot\sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} 1 - \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} l_j \end{aligned} $$ Let us define:

$\displaystyle \text{cnt}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} 1$ : the number of intervals $[l_j,r_j]$ such that $l_j \le i \le r_j, \quad \forall \; 1 \le i \le n$.
$\displaystyle \text{sum}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^{q} l_j$ : the sum of $l_j$ over all intervals $[l_j,r_j]$ such that $l_j \le i \le r_j, \quad \forall \; 1 \le i \le n$.

We can rewrite the expression for $\text{val}_i$ as: $$(i+1)\cdot\text{cnt}_i - \text{sum}_i$$ To efficiently build the $\text{cnt}$ and $\text{sum}$ arrays, we use the technique of Difference Array:

Initialize with all zeros.
For every interval $[l_j,r_j]$, we update:
- $\text{cnt}_{l_j} \gets \text{cnt}_{l_j}+1$
- $\text{cnt}_{r_j+1} \gets \text{cnt}_{r_j+1}-1$
- $\text{sum}_{l_j} \gets \text{sum}_{l_j}+l_j$
- $\text{sum}_{r_j+1} \gets \text{sum}_{r_j+1}-l_j$
After processing all the intervals, replace the $\text{cnt}$ and $\text{sum}$ arrays by their prefix sum arrays.

Time Complexity: $O\left(\sum (n+q)\right)$

Code (C++)

AtCoder - Snuke Prime

You are given integers $n$ and $C$.

There are $n$ services. For the $i^{th}$ service:

It is used from day $a_i$ to day $b_i$, inclusive.
If not subscribed, using this service costs $c_i$ yen per day.

There is a subscription plan that costs $C$ yen per day and allows unlimited use of all services during the subscribed days. You may start the subscription to this plan at the beginning of any day and cancel it at the end of any day.

Determine the minimum total cost required to use all services.

Input
The first line contains integers $n \left(1 \le n \le 2\cdot10^5 \right)$ and $C \left(1 \le C \le 10^9 \right)$.
The next $n$ lines contain integers $a_i$, $b_i \left(1 \le a_i \le b_i \le 10^9\right)$ and $c_i \left(1 \le c_i \le 10^9\right)$.

Output
Print the minimum total cost required to use all services.

Sample Input

2 6
1 2 4
2 2 4

Sample Output

Solution

We will use the technique of Coordinate Compression to simplify this problem:

Initialize an empty vector $\text{all}$.
Insert all values of $a_i$ and $b_i$ in $\text{all}$.
Sort $\text{all}$ and erase duplicates from it.
Let $m$ be the final size of the vector $\text{all}$

For each compressed index $i$, there are two distinct parts of days to consider:

The exact day $\text{all}_i$.
The continuous block of days $[\text{all}_i+1, \text{all}_{i+1}-1]$.

We will handle these two parts separately using arrays $\text{end}$ and $\text{mid}$ respectively:

$\displaystyle \text{end}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i \le r_j}}^{n} c_j$ : the total cost of all services active on day $\text{all}_i, \quad \forall \; 0 \le i < m$.
$\displaystyle \text{mid}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i+1 \\[3pt] \text{all}_{i+1}-1 \le r_j}}^{n} c_j$ : the total cost of all services active on every day in $[\text{all}_i+1, \text{all}_{i+1}-1], \quad \forall \; 0 \le i < m-1$.

Basically, the array $\text{end}$ handles individual important days (i.e., days that are either start or end of a service interval) and the array $\text{mid}$ handles continuous stretches (i.e., days that are neither start nor end of any service interval and hence have identical cost).

To efficiently build the $\text{end}$ and $\text{mid}$ arrays, we use the technique of Difference Array:

Initialize with all zeros.
For every service $a_i,b_i,c_i$, find the indices of $a_i$ and $b_i$ in the array $\text{all}$ using binary search to find their compressed values. Let these values be $l_i$ and $r_i$ respectively, we update:
- $\text{end}_{l_i} \gets \text{end}_{l_i}+c_i$
- $\text{end}_{r_i+1} \gets \text{end}_{r_i+1}-c_i$
- $\text{mid}_{l_i} \gets \text{mid}_{l_i}+c_i$
- $\text{mid}_{r_i} \gets \text{mid}_{r_i}-c_i$
After processing all the services, replace the $\text{end}$ and $\text{mid}$ arrays by their prefix sum arrays.

Without considering the subscription plan that costs $C$ yen per day, the total cost required to use all services is given by: $$\sum_{i=0}^{m-1}\text{end}_i + \sum_{i=0}^{m-2}\text{mid}_i\cdot\left(\text{all}_{i+1}-\text{all}_i-1\right)$$ Considering the subscription plan that costs $C$ yen per day, the minimum total cost required to use all services is given by: $$\sum_{i=0}^{m-1}\min\left(\text{end}_i, C\right) + \sum_{i=0}^{m-2}\min\left(\text{mid}_i, C\right)\cdot\left(\text{all}_{i+1}-\text{all}_i-1\right)$$ Time Complexity: $O(n\log n)$

Code (C++)

CSAcademy - Subarray Medians

You are given a permutation $a$ of size $n$. Compute the value of the expression: $$\sum_{\substack{1 \le l \le r \le n \\[3pt] (r - l)\ \text{even}}}l \cdot r \cdot \text{median}(l,r)$$ where $\text{median}(l,r)$ denotes the median of the subarray $[l,r]$.

Input
The first line contains integer $n \left(1 \le n \le 10^4 \right)$.
The next line contains $n$ integers $a_1,a_2,\ldots,a_n \left(1 \le a_i \le n \right)$.

Output
Print the value of the given expression.

Sample Input

5
1 5 2 4 3

Sample Output

Solution

Using the Contribution Technique, we can rewrite the given expression as: $$ \begin{aligned} & \sum_{i=1}^n\sum_{\substack{1 \le l \le i \le r \le n \\[3pt] (r - l)\ \text{even} \\[3pt] \text{median}(l,r)=a_i}}l \cdot r \cdot a_i \\[6pt] =\; & \sum_{i=1}^na_i\cdot\sum_{\substack{1 \le l \le i \le r \le n \\[3pt] (r - l)\ \text{even} \\[3pt] \text{median}(l,r)=a_i}}l \cdot r \end{aligned} $$ To compute the inner summation for a fixed $i$, let us define: $$ b_j = \begin{cases} 1, & \text{if } a_j > a_i \\ 0, & \text{if } a_j = a_i \\ -1, & \text{if } a_j < a_i \end{cases}, \quad \forall \; 1 \le j \le n. $$ The median of an odd length subarray $[l,r]$ will be $a_i$ iff $l \le i \le r$ and $\displaystyle \sum_{j=l}^rb_j = 0$ since this implies that the number of elements $> a_i$ (which have been assigned a value $1$) is equal to the number of elements $< a_i$ (which have been assigned a value $-1$) in the subarray.

Build the prefix sum array $\text{pre}$ of the array $b$. We can rewrite the expression for the inner summation as: $$ \begin{aligned} & \sum_{\substack{1 \le l \le i \le r \le n \\[3pt] \text{pre}_{l-1} = \text{pre}_r}}l \cdot r \\[6pt] =\; & \sum_{r=i}^nr\cdot\sum_{\substack{l=1 \\[3pt] \text{pre}_{l-1} = \text{pre}_r}}^il \\[6pt] =\; & \sum_{r=i}^nr\cdot\text{sum}_{\text{pre}_r} \end{aligned} $$ where $\displaystyle \text{sum}_j = \sum_{\substack{l=1 \\[3pt] \text{pre}_{l-1} = j}}^il$, which can be computed by iterating on $l$ from $1$ to $i$.

Also, $-n \le \text{pre}_k \le n \left(\because \left|b_k\right| \leq 1\right)$ implies that we have to compute $\text{sum}_j$ for $-n \le j \le n$. To avoid using a map, we can do the following modification to the expression for the inner summation: $$\sum_{r=i}^nr\cdot\text{sum}_{\text{pre}_r+n}$$ where $\displaystyle \text{sum}_j = \sum_{\substack{l=1 \\[3pt] \text{pre}_{l-1}+n = j}}^il$. Thus, we have to compute $\text{sum}_j$ for $0 \le j \le 2\cdot n$ which can be stored in an array.

The final expression for the answer is given by: $$\sum_{i=1}^na_i\cdot \sum_{r=i}^nr\cdot\text{sum}_{\text{pre}_r+n}$$ Time Complexity: $O(n^2)$

Code (C++)

CodeChef - Sum of Cube

You are given $n$ integers $a_1,a_2,\ldots,a_n$. Compute the value of the expression: $$\sum_{i = 1}^n\sum_{j = i}^n\left(\sum_{k = i}^ja_k\right)^3$$ Since the value can be huge, print it modulo $998244353$.

Input
The first line contains integer $t \left(1 \le t \le 10^5\right)$.
The first line of each test case contains integer $n \left(1 \le n \le 5\cdot10^5 \right)$.
The next line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n \left(1 \le a_i \le 10^6\right)$.

Additionally, the following holds true:

The sum of $n$ over all test cases doesn't exceed $5\cdot10^5$.

Output
For each test case, print the value of the given expression modulo $998244353$.

Sample Input

Sample Output

10
128
42621

Solution

NOTE: This solution uses the concept of Changing the Order of Summation. There exists another solution to this problem which is explained in the Combinatorics section.

Build the prefix sum array $\text{pre}$ of the array $a$. Also build the prefix sum array $\text{pre2}$ of the array $\text{pre}$.

We can rewrite the given expression as: $$ \begin{aligned} & \sum_{i = 1}^n\sum_{j = i}^n\left(\text{pre}_j - \text{pre}_{i-1}\right)^3 \\[6pt] =\; & \sum_{i = 1}^n\sum_{j = i}^n\left(\text{pre}_j^3 - \text{pre}_{i-1}^3 - 3\cdot \text{pre}_j^2 \cdot \text{pre}_{i-1} + 3\cdot \text{pre}_j \cdot \text{pre}_{i-1}^2\right) \\[6pt] =\; & S_1 - S_2 - 3\cdot S_3 + 3\cdot S_4 \end{aligned} $$ Simplifying the expression for $S_1$: $$ \sum_{i = 1}^n\sum_{j = i}^n\text{pre}_j^3 = \sum_{j = 1}^n\sum_{i = 1}^j\text{pre}_j^3 = \sum_{j=1}^n\text{pre}_j^3\cdot\sum_{i=1}^j1 = \sum_{j=1}^n\text{pre}_j^3\cdot j $$ Simplifying the expression for $S_2$: $$ \sum_{i = 1}^n\sum_{j = i}^n\text{pre}_{i-1}^3 = \sum_{i=1}^n\text{pre}_{i-1}^3\cdot\sum_{j=i}^n1 = \sum_{i=1}^n\text{pre}_{i-1}^3\cdot(n-i+1) $$ Simplifying the expression for $S_3$: $$ \sum_{i = 1}^n\sum_{j = i}^n\text{pre}_j^2\cdot\text{pre}_{i-1} = \sum_{j = 1}^n\sum_{i = 1}^j\text{pre}_j^2\cdot\text{pre}_{i-1} = \sum_{j = 1}^n\text{pre}_j^2\cdot\sum_{i = 1}^j\text{pre}_{i-1} = \sum_{j = 1}^n\text{pre}_j^2\cdot\text{pre2}_{j-1} $$ Simplifying the expression for $S_4$: $$ \sum_{i = 1}^n\sum_{j = i}^n\text{pre}_j\cdot\text{pre}_{i-1}^2 = \sum_{i = 1}^n\text{pre}_{i-1}^2\cdot\sum_{j = i}^n\text{pre}_j = \sum_{i = 1}^n\text{pre}_{i-1}^2\cdot(\text{pre2}_n - \text{pre2}_{i-1}) $$ Time Complexity: $O(\sum n)$

Code (C++)

AtCoder - Manhattan Multifocal Ellipse

You are given $n$ integer points $(x_i,y_i)$ on a two-dimensional plane, and a non-negative integer $D$.

Find the number of integer pairs $(x,y)$ such that: $$\sum_{i = 1}^n\left(\left|x - x_i\right| + \left|y - y_i\right|\right) \leq D$$
Input
The first line contains integers $n \left(1 \le n \le 2\cdot10^5\right)$ and $D \left(0 \le D \le 10^6 \right)$.
The next $n$ lines contain integers $x_i$ and $y_i \left(-10^6 \le x_i,y_i \le 10^6\right)$.

Additionally, the following holds true:

$(x_i,y_i) \neq (x_j,y_j)$ for $i \neq j$.

Output
Print the number of integer pairs $(x,y)$ satisfying the given condition.

Sample Input

2 3
0 0
1 0

Sample Output

Solution

Let us define:

$\displaystyle f(x) = \sum_{i=1}^n\left|x-x_i\right|$, $\quad \forall \; 1 \le i \le n$.
$\displaystyle g(y) = \sum_{i=1}^n\left|y-y_i\right|$, $\quad \forall \; 1 \le i \le n$.

Also, $\left|x-x_i\right| \le D \Rightarrow x_i - D \le x \le x_i + D$. Since $\min x_i = -10^6$, $\max x_i = 10^6$ and $\max D = 10^6$, we have $-2\cdot 10^6 \le x \le 2\cdot 10^6$. To make our computations simpler, we add a value $2\cdot 10^6$ to each $x_i$ so that $0 \le x \le 4\cdot 10^6$. Similarly we add a value $2\cdot 10^6$ to each $y_i$ so that $0 \le y \le 4\cdot 10^6$.

We have to count the number of integer pairs $(x,y)$ such that:

$0 \le x, y \le N$ where $N= 4\cdot10^6$
$f(x)+g(y) \le D$

Let us understand how to compute $f(x)$ efficiently. Build the arrays $\text{cnt}$ and $\text{sum}$ as:

$\displaystyle \text{cnt}_j = \sum_{\substack{i = 1 \\[3pt] x_i \le j}}^n1$ : the number of $x_i \le j$, $\quad \forall\; 0 \le j \le N$.
$\displaystyle \text{sum}_j = \sum_{\substack{i = 1 \\[3pt] x_i \le j}}^nx_i$ : the sum of $x_i \le j$, $\quad \forall\; 0 \le j \le N$.

We can rewrite the expression for $f(x)$ as: $$ \begin{aligned} & \sum_{\substack{i=1 \\[3pt] x_i \le x}}^n(x-x_i) + \sum_{\substack{i=1 \\[3pt] x_i > x}}^n(x_i-x) \\[6pt] =\; & \sum_{\substack{i=1 \\[3pt] x_i \le x}}^nx - \sum_{\substack{i=1 \\[3pt] x_i \le x}}^nx_i + \sum_{\substack{i=1 \\[3pt] x_i > x}}^nx_i - \sum_{\substack{i=1 \\[3pt] x_i > x}}^nx \\[6pt] =\; & x\cdot\sum_{\substack{i=1 \\[3pt] x_i \le x}}^n1 - \sum_{\substack{i=1 \\[3pt] x_i \le x}}^nx_i + \sum_{\substack{i=1 \\[3pt] x_i > x}}^nx_i - x\cdot\sum_{\substack{i=1 \\[3pt] x_i > x}}^n1 \\[6pt] =\; & x\cdot\text{cnt}_x - \text{sum}_x + (\text{sum}_N - \text{sum}_x) - x\cdot(\text{cnt}_N - \text{cnt}_x) \\[6pt] =\; & \text{sum}_N - 2\cdot\text{sum}_x + 2\cdot x\cdot\text{cnt}_x - x\cdot\text{cnt}_N \\[6pt] =\; & \text{sum}_N - 2\cdot\text{sum}_x + 2\cdot x\cdot\text{cnt}_x - x\cdot n \end{aligned} $$ Thus, we can compute $f(x)$ for some fixed $x$ in $O(1)$ using the arrays $\text{cnt}$ and $\text{sum}$. Similarly, we can build the arrays $\text{cnt}$ and $\text{sum}$ over $y_i$ for computing $g(y)$.

To count the number of integer pairs $(x,y)$ satisfying the given conditions, follow the steps:

Store the values of $g(y)$ for $0 \le y \le N$ in a vector $\text{all}$ and sort it.
Iterate on $x$ from $0$ to $N$, and compute the value of $f(x)$. The inequality $f(x)+g(y) \le D$ implies that $g(y) \le D-f(x)$. Use binary search in the vector $\text{all}$ to count the number of elements $\le D-f(x)$. This count gives us the number of integers $y$ for a fixed $x$ such that $f(x)+g(y) \le D$. Final answer is the sum of this count over all $x$.

Time Complexity: $O(N\log N)$

Code (C++)

2D Prefix Sum

Given a 2D array $a$ of size $n \times m$, the prefix sum array $\text{pre}$ is defined as:

\[\text{pre}_{i,j} = \sum_{x=1}^i\sum_{y=1}^ja_{x,y}, \quad \forall \; 1 \le i \le n, 1 \le j \le m\]

That is, $\text{pre}_{i,j}$ stores the sum of all elements in the submatrix with top-left corner $(1,1)$ and bottom-right corner $(i,j)$.

This array can be computed iteratively in $O(n\cdot m)$ time using the following relations:

\[\begin{aligned} & \text{pre}_{0,j} = 0, \quad \forall \; 0 \le j \le m \\[6pt] & \text{pre}_{i,0} = 0, \quad \forall \; 0 \le i \le n \\[6pt] & \text{pre}_{i,j} = \text{pre}_{i-1,j} + \text{pre}_{i,j-1} - \text{pre}_{i-1,j-1} + a_{i,j}, \quad \forall \; 1 \le i \le n, 1 \le j \le m \end{aligned}\]

The most common application of this array is computing the sum of elements in a submatrix with top-left corner $(x_1,y_1)$ and bottom-right corner $(x_2,y_2)$ in $O(1)$ time using the fact:

\[\sum_{x=x_1}^{x_2}\sum_{y=y_1}^{y_2}a_{x,y} = \text{pre}_{x_2,y_2} - \text{pre}_{x_1-1,y_2} - \text{pre}_{x_2, y_1-1} + \text{pre}_{x_1-1,y_1-1}\]

To gain a much better understanding of this visually, do check out the interactive widget on the USACO Guide.

For completeness, the mathematical derivation is provided below:

\[\begin{aligned} & \sum_{x=x_1}^{x_2}\sum_{y=y_1}^{y_2}a_{x,y} \\[6pt] =\; & \sum_{x=x_1}^{x_2}\left(\sum_{y=1}^{y_2}a_{x,y} - \sum_{y=1}^{y_1-1}a_{x,y}\right) \\[6pt] =\; & \sum_{x=x_1}^{x_2}\sum_{y=1}^{y_2}a_{x,y} - \sum_{x=x_1}^{x_2}\sum_{y=1}^{y_1-1}a_{x,y} \\[6pt] =\; & \left(\sum_{x=1}^{x_2}\sum_{y=1}^{y_2}a_{x,y} - \sum_{x=1}^{x_1-1}\sum_{y=1}^{y_2}a_{x,y}\right) - \left(\sum_{x=1}^{x_2}\sum_{y=1}^{y_1-1}a_{x,y} - \sum_{x=1}^{x_1-1}\sum_{y=1}^{y_1-1}a_{x,y}\right) \\[6pt] =\; & \text{pre}_{x_2,y_2} - \text{pre}_{x_1-1,y_2} - \text{pre}_{x_2,y_1-1} + \text{pre}_{x_1-1,y_1-1} \end{aligned}\]

Learn Through Problems

CSES - Forest Queries

You are given an $n \times n$ grid. Each cell $a_{i,j}$ is either empty or contains a tree.

You have to answer $q$ queries. In each query, you are given a rectangle defined by its corners $(y_1, x_1)$ and $(y_2, x_2)$, and you have to determine the number of cells containing a tree inside the rectangle.

Input
The first line contains integers $n \left(1 \le n \le 10^3 \right)$ and $q \left(1 \le q \le 2\cdot10^5 \right)$.
The next $n$ lines contain a string of length $n$ where an empty cell is defined by $.$ and a tree is defined by $*$.
The next $q$ lines contain integers $y_1$, $x_1$, $y_2$, $x_2 \left(1 \le y_1 \le y_2 \le n, 1 \le x_1 \le x_2 \le n \right)$.

Output
For each query, print the number of cells containing a tree inside the rectangle.

Sample Input

4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2

Sample Output

3
1
2

Solution

Build the prefix sum array $\text{pre}$ of the grid $a$ considering $a_{i,j} = 1$ if it contains a tree and $a_{i,j} = 0$ if its empty.

The number of trees inside the rectangle defined by $(y_1,x_1)$ and $(y_2,x_2)$ is given by: $$\text{pre}_{y_2,x_2} - \text{pre}_{y_1-1,x_2} - \text{pre}_{y_2,x_1-1} + \text{pre}_{y_1-1,x_1-1}$$ Time Complexity: $O(n^2 + q)$

Code (C++)

Codeforces - 2D Difference Array

You are given an $n \times m$ grid. Let $a_{i,j}$ denote the value of the cell at the $i^{th}$ row from the top and the $j^{th}$ column from the left. Initially, each cell has a value $0$.

Perform $q$ operations on this grid:

The $i^{th}$ operation is described by integers $a_i,b_i,c_i,d_i,w_i$.
In the $i^{th}$ operation, for every $j,k$ such that $a_i \le j \le b_i$ and $c_i \le k \le d_i$, update $a_{j,k} \gets a_{j,k}+w_i$.

Find the final state of the grid after performing all $q$ operations.

Input
The first line contains integers $n$, $m \left(1 \le n,m \le 10^3 \right)$ and $q \left(1 \le q \le 10^5 \right)$.
The next $q$ lines contain integers $a_i$, $b_i \left(1 \le a_i,b_i \le n \right)$, $c_i$, $d_i \left(1 \le c_i,d_i \le m \right)$ and $w_i \left(0 \le w_i \le 10^9 \right)$.

Output
Print the final state of the grid after performing all $q$ operations.

Sample Input

Sample Output

5 5 5
8 12 9
3 7 4

Solution

Let us define:

$\displaystyle \text{val}_{i,j} = \sum_{\substack{k=1 \\ a_k \le i \le b_k \\ c_k \le j \le d_k}}^q{w_k}$: the value of $a_{i,j}$ after all $q$ operations, $\quad \forall \; 1 \le i \le n, 1 \le j \le m$.

To efficiently build the $\text{val}$ array, we use the technique of Difference Array:

Initialize with all zeros.
For every query $a_i,b_i,c_i,d_i,w_i$, we update:
- $\text{val}_{a_i,c_i} \gets \text{val}_{a_i,c_i} + w_i$
- $\text{val}_{a_i,d_i+1} \gets \text{val}_{a_i,d_i+1} - w_i$
- $\text{val}_{b_i+1,c_i} \gets \text{val}_{b_i+1,c_i} - w_i$
- $\text{val}_{b_i+1,d_i+1} \gets \text{val}_{b_i+1,d_i+1} + w_i$
After processing all the queries, replace the $\text{val}$ array with its prefix sum array.

The logic of this technique extended to 2D is left as an exercise for you.

Time Complexity: $O(n\cdot m + q)$

Code (C++)

Practice Problems

CSES - Range XOR Queries

CSES - Subarray Divisibility
Solution
Formally, we have to count the number of pairs $(l,r)$ such that:
- $1 \le l \le r \le n$
- $\displaystyle \sum_{i=l}^ra_i \bmod n = 0$
Build the prefix sum array $\text{pre}$ of the array $a$. Now the second condition can be written as: $$ \begin{aligned} & \left(\text{pre}_r - \text{pre}_{l-1}\right) \bmod n = 0 \\[6pt] \Rightarrow\; & \text{pre}_{l-1} \bmod n = \text{pre}_r \bmod n \end{aligned} $$ Replacing $l \rightarrow l+1$, we can rewrite both the conditions as:
- $0 \le l < r \le n$
- $\text{pre}_l \bmod n = \text{pre}_r \bmod n$
To count the number of pairs $(l,r)$ satisfying this, we can iterate on $r$ from $1$ to $n$ and keep track of the frequencies of $\text{pre}_l \bmod n$ for $0 \le l < r$.

Time Complexity: $O(n)$
Code (C++)
Codeforces - Good Subarrays
Solution
Formally, we have to count the number of pairs $(l,r)$ such that:
- $1 \le l \le r \le n$
- $\displaystyle \sum_{i=l}^ra_i = r-l+1$
Build the prefix sum array $\text{pre}$ of the array $a$. Now the second condition can be written as: $$ \begin{aligned} & \text{pre}_r - \text{pre}_{l-1} = r-l+1 \\[6pt] \Rightarrow\; & \text{pre}_{l-1} - (l-1) = \text{pre}_r - r \end{aligned} $$ Replacing $l \rightarrow l+1$, we can rewrite both the conditions as:
- $0 \le l < r \le n$
- $\text{pre}_{l}-l = \text{pre}_r-r$
To count the number of pairs $(l,r)$ satisfying this, we can iterate on $r$ from $1$ to $n$ and keep track of the frequencies of $\text{pre}_l-l$ for $0 \le l < r$.

Also, $0 \le \text{pre}_i \le 9\cdot n$ and $0 \le i \le n$ $\Rightarrow -n \le \text{pre}_i-i \le 9\cdot n$. To store the frequencies of $\text{pre}_i-i$ in an array and avoid using a map, we can add a value $n$ to it so that $0 \le \text{pre}_i-i+n \le 10\cdot n$.

Time Complexity: $O(\sum{n})$
Code (C++)
AtCoder - Not All Covered
Solution
Let us define:
- $\displaystyle \text{freq}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le i \le r_j}}^M1$: the number of turrets which guard the castle wall $i$, $\quad \forall \; 1 \le i \le N$.
To efficiently build the $\text{freq}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every turret $[l_i,r_i]$, we update:
  
  $\text{freq}_{l_i} \gets \text{freq}_{l_i}+1$
  
  $\text{freq}_{r_i+1} \gets \text{freq}_{r_i+1}-1$
- After processing all the turrets, replace the $\text{freq}$ array with its prefix sum array.
For a castle wall $i$, the minimum number of turrets that need to be destroyed so that it is not guarded by any turret is $\text{freq}_i$.

Thus, the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret is given by: $$\min_{1 \le i \le N}\text{freq}_i$$ Time Complexity: $O(N+M)$
Code (C++)
AtCoder - Lamps
Solution
First, let us understand how to efficiently simulate $1$ operation.

Let us define:
- $\displaystyle \text{sum}_i = \sum_{\substack{j=1 \\ |j-i| \le A_j}}^N1$: the number of bulbs illuminating coordinate $i$, $\quad \forall \; 1 \le i \le N$.
To efficiently build the $\text{sum}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every bulb $j$, define $l_j = \max(j-A_j,1)$, $r_j = \min(j+A_j,N)$, we update:
  
  $\text{sum}_{l_j} \gets \text{sum}_{l_j} + 1$
  
  $\text{sum}_{r_j+1} \gets \text{sum}_{r_j+1} - 1$
- After processing all the bulbs, replace the $\text{sum}$ array with its prefix sum array.
So, after $1$ operation, the array $A$ becomes the array $\text{sum}$. If we repeat this process $K$ times, it will take $O(N\cdot K)$ time which won't run in the given time limit.

FACT: After $O(\log N)$ operations, the array $A$ converges to $N,N,\ldots,N$.

To get a rough explanation of this, please read the Atcoder Editorial. Thus, we need to apply the operation at most $O(\log N)$ times.

Time Complexity: $O(N\log N)$
Code (C++)
Codeforces - Constant Palindrome Sum
Solution
Let us define:
- $\text{val}_i$: the minimum number of elements we need to replace so that $a_j + a_{n-j+1} = i \; \forall \; 1 \le j \le \frac{n}{2}$, $\quad \forall \; 1 \le i \le 2\cdot k$.
Also, we will assume that $a_j \le a_{n-j+1} \; \forall \; 1 \le j \le \frac{n}{2}$, if not then we can swap the elements.

We have the following three cases for each pair $(a_j,a_{n-j+1})$:
- Case 1: None of the elements need to be replaced.
  
  To attain the sum $a_j + a_{n-j+1} = x$, none of the elements need to be replaced. Thus, we don't make any updates.
- Case 2: Exactly one of the elements needs to be replaced.
  
  To attain all the sums in range $[a_j + 1, a_{n-j+1} + k]$, except the current sum $a_j + a_{n-j+1} = x$, exactly one of the elements needs to be replaced. Thus, we update: $$\text{val}_i \gets \text{val}_i + 1, \quad \forall \; i \in [a_j + 1, a_{n-j+1} + k] \setminus \{x\}$$
- Case 3: Both the elements need to be replaced.
  
  To attain all the sums in range $[2, 2\cdot k]$, except the ones which can be attained by replacing at most one of the elements, i.e., $[a_j + 1, a_{n-j+1} + k]$, both the elements need to be replaced. Thus, we update: $$\text{val}_i \gets \text{val}_i + 2, \quad \forall \; i \in [2, 2\cdot k] \setminus [a_j + 1, a_{n-j+1} + k]$$
To efficiently build the $\text{val}$ array, we can use the technique of Difference Array:
- Initialize with all zeros.
- For every pair $(a_j, a_{n-j+1})$, to add a value $d$ to a range of indices $[l,r]$, we update:
  
  $\text{val}_l \gets \text{val}_l + d$
  
  $\text{val}_{r+1} \gets \text{val}_{r+1} - d$
- After processing all the pairs, replace the $\text{val}$ array with its prefix sum array.
The minimum number of elements we need to replace to satisfy the given conditions is given by: $$\min_{2 \le i \le 2\cdot k}\text{val}_i$$ Time Complexity: $O(\sum(n+k))$
Code (C++)
Codeforces - Greg and Array
Solution
Let us define:
- $\displaystyle \text{freq}_i = \sum_{\substack{j=1 \\[3pt] x_j \le i \le y_j}}^k1$: the number of times operation $i$ needs to be applied, $\quad \forall \; 1 \le i \le m$.
- $\displaystyle \text{sum}_i = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j}}^md_j$: the total value added to $a_i$ after applying all operations, $\quad \forall \; 1 \le i \le n$.
To efficiently build the $\text{freq}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every query $[x_i,y_i]$, we update:
  
  $\text{freq}_{x_i} \gets \text{freq}_{x_i} + 1$
  
  $\text{freq}_{y_i+1} \gets \text{freq}_{y_i+1} - 1$
- After processing all the queries, replace the $\text{freq}$ array with its prefix sum array.
To efficiently build the $\text{sum}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every operation $[l_i,r_i,d_i]$, we update:
  
  $\text{sum}_{l_i} \gets \text{sum}_{l_i} + d_i\cdot \text{freq}_i$
  
  $\text{sum}_{r_i+1} \gets \text{sum}_{r_i+1} - d_i\cdot \text{freq}_i$
- After processing all the operations, replace the $\text{sum}$ array with its prefix sum array.
After applying all operations, the value of element at index $i$ is given by $a_i + \text{sum}_i$.

Time Complexity: $O(n+m+k)$
Code (C++)
Codeforces - Little Girl and Maximum Sum
Solution
Let us define:
- $\displaystyle \text{freq}_i = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j}}^q1$: the number of queries to which the index $i$ belongs, $\quad \forall \; 1 \le i \le n$.
To efficiently build the $\text{freq}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every query $[l_i,r_i]$, we update:
  
  $\text{freq}_{l_i} \gets \text{freq}_{l_i}+1$
  
  $\text{freq}_{r_i+1} \gets \text{freq}_{r_i+1}-1$
- After processing all the queries, replace the $\text{freq}$ array with its prefix sum array.
Let $(b_1,b_2,\ldots,b_n)$ be a permutation of $(a_1,a_2,\ldots,a_n)$. We have to maximize the value of the following expression: $$\sum_{i=1}^n(b_i \cdot \text{freq}_i)$$ I claim that the maximum value of this expression is attained when both the arrays $b$ and $\text{freq}$ are sorted. The proof of this claim is given in the Exchange Arguments section.

Thus, we can sort both the arrays $a$ and $\text{freq}$, and calculate the value of the above expression to get the answer.

Time Complexity: $O(n \log n)$
Code (C++)
Codeforces - Number of Ways
Solution
Formally, we have to count the number of pairs $(l,r)$ such that:
- $2 \le l \le r < n$
- $\displaystyle \sum_{i=1}^{l-1}a_i = \sum_{i=l}^ra_i = \sum_{i=r+1}^na_i$
Build the prefix sum array $\text{pre}$ of the array $a$. Now the second condition can be written as: $$ \begin{aligned} & \text{pre}_{l-1} = \text{pre}_r - \text{pre}_{l-1} = \text{pre}_n - \text{pre}_r \\[6pt] \Rightarrow\; & \text{pre}_{l-1} = \frac{\text{pre}_n}{3}, \quad \text{pre}_r = \frac{2\cdot \text{pre}_n}{3} \\[6pt] \Rightarrow\; & 3\cdot \text{pre}_{l-1} = \text{pre}_n, \quad 3\cdot \text{pre}_r = 2\cdot \text{pre}_n \end{aligned} $$ Replacing $l \rightarrow l+1$, we can rewrite both the conditions as:
- $1 \le l < r < n$
- $3\cdot \text{pre}_l = \text{pre}_n, \quad 3\cdot \text{pre}_r = 2\cdot \text{pre}_n$
To count the number of pairs $(l,r)$ satisfying this, we can iterate on $r$ from $2$ to $n-1$ and keep track of the count of $l$ such that $1 \le l < r$ and $3\cdot \text{pre}_l = \text{pre}_n$.

Time Complexity: $O(n)$
Code (C++)

Codeforces - Matrix Cascade

Codeforces - Unique Median

Codeforces - Yamakasi

Codeforces - Gangsta
Solution
Build the prefix sum array $\text{pre}$ of the string $s$. We can write the expression for $f(s_ls_{l+1}\ldots s_r)$ as: $$ \max(\text{pre}_r - \text{pre}_{l-1}, r-l+1-(\text{pre}_r - \text{pre}_{l-1})) $$ FACT: $\displaystyle \max(a,b) = \frac{a+b+|a-b|}{2}$

Using this fact, we can rewrite the above expression as: $$ \frac{r-l+1 + |(2\cdot \text{pre}_r - r) - (2\cdot \text{pre}_{l-1} - (l-1))|}{2} $$ Let us define:
- $g_i = 2\cdot \text{pre}_i - i, \quad \forall \; 0 \le i \le n$.
We can rewrite the above expression as: $$ \frac{r-l+1 + |g_r - g_{l-1}|}{2} $$ We have to compute the value of the expression: $$ \begin{aligned} & \sum_{l=1}^n\sum_{r=l}^nf(s_ls_{l+1}\ldots s_r) \\[6pt] =\; & \sum_{l=1}^n\sum_{r=l}^n\left(\frac{r-l+1 + |g_r - g_{l-1}|}{2}\right) \\[6pt] =\; & \frac{1}{2} \left(\sum_{l=1}^n\sum_{r=l}^n(r-l+1) + \sum_{l=1}^n\sum_{r=l}^n|g_r - g_{l-1}|\right) \\[6pt] =\; & \frac{1}{2} (S_1 + S_2) \end{aligned} $$ Using the Contribution Technique, we can rewrite the expression for $S_1$ as: $$\sum_{i=1}^ni\cdot (n-i+1)$$ since there are exactly $n-i+1$ segments of length $i$.

After sorting the array $g$, we can rewrite the expression for $S_2$ as: $$\sum_{l=1}^n\sum_{r=l}^n(g_r - g_{l-1})$$ Using the Contribution Technique, we can rewrite this expression as: $$\sum_{i=0}^ng_i\cdot (i-(n-i))$$ since $g_i$ occurs in exactly $i$ terms with a positive sign, and in exactly $n-i$ terms with a negative sign, among all the terms $g_r-g_{l-1}$.

Time Complexity: $O(\sum(n\log n))$
Code (C++)
Codeforces - Running Miles
Solution
Notice that two of the maximums should be at the ends of the range $[l,r]$, otherwise we can move at least one of the boundaries closer to the other and get a better answer.

Formally, we have to compute the value of the expression: $$ \begin{aligned} & \max_{1 \le l < i < r \le n}\left(b_l + b_i + b_r - (r-l)\right) \\[6pt] =\; & \max_{1 < i < n}\left(b_i + \max_{1 \le l < i}(b_l+l) + \max_{i < r \le n}(b_r-r)\right) \\[6pt] \end{aligned} $$ Let us define:
- $\displaystyle \text{pre}_i = \max_{1 \le j \le i}(b_j + j), \quad \forall \; 1 \le i \le n$.
- $\displaystyle \text{suf}_i = \max_{i \le j \le n}(b_j - j), \quad \forall \; 1 \le i \le n$.
We can rewrite the above expression as: $$\max_{1 < i < n}\left(b_i + \text{pre}_{i-1} + \text{suf}_{i+1}\right)$$ To efficiently build the $\text{pre}$ and $\text{suf}$ arrays, use the following relations: $$ \begin{aligned} & \text{pre}_1 = b_1 + 1 \\[6pt] & \text{pre}_i = \max(\text{pre}_{i-1}, b_i+i), \quad \forall \; 1 < i \le n \\[6pt] & \text{suf}_n = b_n - n \\[6pt] & \text{suf}_i = \max(\text{suf}_{i+1}, b_i-i), \quad \forall \; 1 \le i < n \end{aligned} $$ Time Complexity: $O(\sum{n})$
Code (C++)
Codeforces - The Union of k-Segments
Solution
We will use the technique of Coordinate Compression to simplify this problem:
- Initialize an empty vector $\text{all}$.
- Insert all values of $l_i$ and $r_i$ in $\text{all}$.
- Sort $\text{all}$ and erase duplicates from it.
- Let $m$ be the final size of the vector $\text{all}$
For each compressed index $i$, there are two distinct parts of points to consider:
- The exact point $\text{all}_i$.
- All the points in $(\text{all}_i, \text{all}_{i+1})$.
We will handle these two parts separately using arrays $\text{end}$ and $\text{mid}$ respectively:
- $\displaystyle \text{end}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i \le r_j}}^{n} 1$ : the number of segments $[l_j,r_j]$ containing the point $\text{all}_i, \quad \forall \; 0 \le i < m$.
- $\displaystyle \text{mid}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i \\[3pt] \text{all}_{i+1} \le r_j}}^{n} 1$ : the number of segments $[l_j,r_j]$ containing all the points in $(\text{all}_i, \text{all}_{i+1}), \quad \forall \; 0 \le i < m-1$.
To efficiently build the $\text{end}$ and $\text{mid}$ arrays, we use the technique of Difference Array:
- Initialize with all zeros.
- For every segment $l_i,r_i$, find the indices of $l_i$ and $r_i$ in the array $\text{all}$ using binary search to find their compressed values. Let these values be $L_i$ and $R_i$ respectively, we update:
  
  $\text{end}_{L_i} \gets \text{end}_{L_i}+1$
  
  $\text{end}_{R_i+1} \gets \text{end}_{R_i+1}-1$
  
  $\text{mid}_{L_i} \gets \text{mid}_{L_i}+1$
  
  $\text{mid}_{R_i} \gets \text{mid}_{R_i}-1$
- After processing all the segments, replace the $\text{end}$ and $\text{mid}$ arrays by their prefix sum arrays.
Using the $\text{end}$ and $\text{mid}$ arrays we can easily construct the smallest set of segments which contains all the points that belong at least k segments. For more details, take a look at the implementation.

Time Complexity: $O(n \log n)$
Code (C++)
Codeforces - Mike and Geometry Problem
Solution
We will use the technique of Coordinate Compression to simplify this problem:
- Initialize an empty vector $\text{all}$.
- Insert all values of $l_i$ and $r_i$ in $\text{all}$.
- Sort $\text{all}$ and erase duplicates from it.
- Let $m$ be the final size of the vector $\text{all}$
For each compressed index $i$, there are two distinct parts of points to consider:
- The exact point $\text{all}_i$.
- All the points in $[\text{all}_i+1, \text{all}_{i+1}-1]$.
We will handle these two parts separately using arrays $\text{end}$ and $\text{mid}$ respectively:
- $\displaystyle \text{end}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i \le r_j}}^{n} 1$ : the number of segments $[l_j,r_j]$ containing the point $\text{all}_i, \quad \forall \; 0 \le i < m$.
- $\displaystyle \text{mid}_i = \sum_{\substack{j = 1 \\[3pt] l_j \le \text{all}_i+1 \\[3pt] \text{all}_{i+1}-1 \le r_j}}^{n} 1$ : the number of segments $[l_j,r_j]$ containing all the points in $[\text{all}_i+1, \text{all}_{i+1}-1], \quad \forall \; 0 \le i < m-1$.
To efficiently build the $\text{end}$ and $\text{mid}$ arrays, we use the technique of Difference Array:
- Initialize with all zeros.
- For every segment $l_i,r_i$, find the indices of $l_i$ and $r_i$ in the array $\text{all}$ using binary search to find their compressed values. Let these values be $L_i$ and $R_i$ respectively, we update:
  
  $\text{end}_{L_i} \gets \text{end}_{L_i}+1$
  
  $\text{end}_{R_i+1} \gets \text{end}_{R_i+1}-1$
  
  $\text{mid}_{L_i} \gets \text{mid}_{L_i}+1$
  
  $\text{mid}_{R_i} \gets \text{mid}_{R_i}-1$
- After processing all the segments, replace the $\text{end}$ and $\text{mid}$ arrays by their prefix sum arrays.
Let $\text{ans} = $ the number of points in the intersection of any $k$ of the segments. Notice that if any point $j$ is contained in exactly $i$ segments, then its contribution to the value of $\text{ans}$ will be $\displaystyle \left(\begin{array}{cc} i \\ k \\ \end{array}\right) = \frac{i!}{k!\,(i-k)!}$.

Using the Contribution Technique, we can write the expression for $\text{ans}$ as: $$\sum_{\substack{i=0 \\[3pt] \text{end}_i \ge k}}^{m-1}\left(\begin{array}{cc} \text{end}_i \\ k \\ \end{array}\right) + \sum_{\substack{i=0 \\[3pt] \text{mid}_i \ge k}}^{m-2}\left(\begin{array}{cc} \text{mid}_i \\ k \\ \end{array}\right)\cdot (\text{all}_{i+1}-\text{all}_i-1)$$ Time Complexity: $O(n \log n)$
Code (C++)
Codeforces - Blackslex and Plants
Solution
Let us define:
- $\displaystyle \text{val}_i = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j}}^qf(i-l_j+1)$: the value of plant $i$ after all $q$ operations., $\quad \forall \; 1 \le i \le n$.
Using the definition of $f(x)$, we can rewrite the expression for $\text{val}_i$ as: $$ \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j}}^q{(i-l_j+1)\cdot \text{LSSB}_{i-l_j+1}} $$ where $\text{LSSB}_x$ is the value of the least significant set bit of $x$.

Also, $1 \le i-l_j+1 \le n$ $\Rightarrow$ $\text{LSSB}_{i-l_j+1} \in \left\{2^0, 2^1, \ldots, 2^N\right\}$ where $N=\left\lfloor \log n \right\rfloor$. Using the Contribution Technique, we can rewrite the expression for $\text{val}_i$ as: $$ \begin{aligned} & \sum_{k=0}^N\sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^q{(i-l_j+1)\cdot 2^k} \\[6pt] =\; & \sum_{k=0}^N{2^k \cdot \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^q(i-l_j+1)} \\[6pt] =\; & \sum_{k=0}^N{2^k \cdot \left((i+1)\cdot \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^q1 - \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^ql_j\right)} \\[6pt] \end{aligned} $$ Let us define:
- $\displaystyle \text{cnt}_{k,i} = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^q1$: the number of operations $[l_j,r_j]$ such that $l_j \le i \le r_j$ and $\text{LSSB}_{i-l_j+1}=2^k$, $\quad \forall \; 0 \le k \le N, 1 \le i \le n$.
- $\displaystyle \text{sum}_{k,i} = \sum_{\substack{j=1 \\[3pt] l_j \le i \le r_j \\[3pt] \text{LSSB}_{i-l_j+1}=2^k}}^ql_j$: the sum of $l_j$ over all operations $[l_j,r_j]$ such that $l_j \le i \le r_j$ and $\text{LSSB}_{i-l_j+1}=2^k$, $\quad \forall \; 0 \le k \le N, 1 \le i \le n$.
We can rewrite the expression for $\text{val}_i$ as: $$\sum_{k=0}^N{2^k \cdot \left((i+1)\cdot \text{cnt}_{k,i} - \text{sum}_{k,i}\right)}$$ FACT: For any positive integer $x$, $\text{LSSB}_x = 2^k$ $(k \ge 0)$ iff $x$ is an odd multiple of $2^k$; formally $\exists\; m \in {\mathbb{Z}}_{\geq 0}$ such that: $$x = 2^k \cdot (2\cdot m + 1) = 2^{k+1} \cdot m + 2^k$$ Using this fact, we can simplify the $\text{LSSB}$ condition as: $$ \begin{aligned} & \text{LSSB}_{i-l_j+1} = 2^k \\[6pt] \iff & i-l_j+1 \in \{2^{k+1}\cdot m+2^k \mid m \in \mathbb{Z}_{\geq 0}\} \\[6pt] \iff & i \in \{2^{k+1}\cdot m+2^k+l_j-1 \mid m \in \mathbb{Z}_{\geq 0}\} \end{aligned} $$ This is an arithmetic progression with first term $2^k + l_j-1$ and common difference $2^{k+1}$.

From the above analysis we can conclude that for an operation $[l_j,r_j]$, we want to make the following updates efficiently to build the $\text{cnt}$ and $\text{sum}$ arrays: $$ \begin{aligned} & \text{cnt}_{k,i} \gets \text{cnt}_{k,i} + 1, \quad \forall \; 0 \le k \le N, i \in \{2^{k+1}\cdot m+2^k+l_j-1 \mid m \in \mathbb{Z}_{\geq 0}\} \cap \{l_j,l_j+1,\ldots,r_j\} \\[6pt] & \text{sum}_{k,i} \gets \text{sum}_{k,i} + l_j, \quad \forall \; 0 \le k \le N, i \in \{2^{k+1}\cdot m+2^k+l_j-1 \mid m \in \mathbb{Z}_{\geq 0}\} \cap \{l_j,l_j+1,\ldots,r_j\} \end{aligned} $$ This is equivalent to adding a fixed value to a set of indices $i$ in range $[l_j,r_j]$ which are part of an arithmetic progression having first term $2^k + l_j - 1$ and common difference $2^{k+1}$.

NOTE: I recommend you to stop here and think about how to apply the updates efficiently.

To efficiently build the $\text{cnt}$ and $\text{sum}$ arrays, we use the technique of Difference Array:
- Initilize the $\text{cnt}$ and $\text{sum}$ arrays with all zeros.
- For every operation $[l_j,r_j]$, for a fixed value of $k$, define $a = 2^k + l_j - 1$ (first term), $d = 2^{k+1}$ (common difference), let $\textbf{st}$ and $\textbf{end}$ be the minimum and maximum values respectively in the range $[l_j,r_j]$ which are part of this arithmetic progression, we update:
  
  $\text{cnt}_{k,st} \gets \text{cnt}_{k,st} + 1, \quad \forall \; 0 \le k \le N$
  
  $\text{cnt}_{k,end+d} \gets \text{cnt}_{k,end+d} - 1, \quad \forall \; 0 \le k \le N$
  
  $\text{sum}_{k,st} \gets \text{sum}_{k,st} + l_j, \quad \forall \; 0 \le k \le N$
  
  $\text{sum}_{k,end+d} \gets \text{sum}_{k,end+d} - l_j, \quad \forall \; 0 \le k \le N$
- After processing all the operations, first iterate on $k$ from $0$ to $N$, then iterate on $i$ from $d = 2^{k+1}$ to $n$, update:
  
  $\text{cnt}_{k,i} \gets \text{cnt}_{k,i} + \text{cnt}_{k,i-d}$
  
  $\text{sum}_{k,i} \gets \text{sum}_{k,i} + \text{sum}_{k,i-d}$
Time Complexity: $O(\sum((n+q) \log n))$
Code (C++)
AtCoder - Tail of Snake
Solution

Formally, we have to compute the value of the expression: $$\max_{1 \le l < r < N}\left(\sum_{i=1}^lA_i + \sum_{i=l+1}^rB_i + \sum_{i=r+1}^NC_i\right)$$ Build the prefix sum arrays $\text{pre1}$, $\text{pre2}$, $\text{pre3}$ of the arrays $A$, $B$, $C$ respectively. Now we can rewrite the expression as: $$ \begin{aligned} & \max_{1 \le l < r < N}\left(\text{pre1}_l + \text{pre2}_r - \text{pre2}_l + \text{pre3}_N - \text{pre3}_r\right) \\[6pt] =\; & \max_{2 \le r < N}\left(\text{pre3}_N + \text{pre2}_r - \text{pre3}_r + \max_{1 \le l < r}\left(\text{pre1}_l-\text{pre2}_l\right)\right) \end{aligned} $$ To compute this, we can iterate on $r$ from $2$ to $N-1$ and keep track of $\displaystyle \max_{1 \le l < r}\left(\text{pre1}_l-\text{pre2}_l\right)$.

Time Complexity: $O(N)$
Code (C++)
AtCoder - Max/Min
Solution
Let us define:
- $\displaystyle \text{freq}_i = \sum_{\substack{j=1 \\[3pt] A_j = i}}^N1$: the number of times integer $i$ is present in the array $A$, $\quad \forall \; 1 \le i \le M$ where $M = 10^6$.
- $\displaystyle \text{pre}_i = \sum_{j=1}^i\text{freq}_j$: the number of integers $\le i$ present in the array $A$, $\quad \forall \; 1 \le i \le M$.
Using the Contribution Technique, we can rewrite the given expression as: $$ \sum_{i=1}^M{\text{freq}_i\cdot \sum_{j=i+1}^M\left(\text{freq}_j \cdot \left\lfloor \frac{j}{i} \right\rfloor\right)} + \sum_{i=1}^M\left(\begin{array}{cc} \text{freq}_i \\ 2 \\ \end{array}\right) $$ where the second term accounts for the contribution from the case $j = i$.

Using the Contribution Technique again, we can rewrite the given expression as: $$ \begin{aligned} & \sum_{i=1}^M{\text{freq}_i\cdot \sum_{k=1}^{\left\lfloor \frac{M}{i} \right\rfloor}\sum_{\substack{j=i+1 \\[3pt] \left\lfloor \frac{j}{i} \right\rfloor = k}}^M(\text{freq}_j \cdot k)} + \sum_{i=1}^M\left(\begin{array}{cc} \text{freq}_i \\ 2 \\ \end{array}\right) \\[6pt] =\; & \sum_{i=1}^M{\text{freq}_i\cdot \sum_{k=1}^{\left\lfloor \frac{M}{i} \right\rfloor}{k \cdot \sum_{\substack{j=i+1 \\[3pt] \left\lfloor \frac{j}{i} \right\rfloor = k}}^M\text{freq}_j}} + \sum_{i=1}^M\left(\begin{array}{cc} \text{freq}_i \\ 2 \\ \end{array}\right) \end{aligned} $$ We can simplify the floor condition as: $$ \left\lfloor \frac{j}{i} \right\rfloor = k \quad \Rightarrow k \le \frac{j}{i} < k+1 \quad \Rightarrow i\cdot k \le j \le i\cdot (k+1) - 1 $$ Thus, for the innermost summation, we have the following two inequalities for $j$: $$ \begin{aligned} & i+1 \le j \le M \\[6pt] & i\cdot k \le j \le i\cdot (k+1) - 1 \end{aligned} $$ Combining these inequalities gives: $$\max(i+1,i\cdot k) \le j \le \min(M,i\cdot (k+1)-1)$$ Let us define:
- $l_{i,k} = \max(i+1,i\cdot k), \quad \forall \; 1 \le i \le M, 1 \le k \le \left\lfloor \frac{M}{i} \right\rfloor$
- $r_{i,k} = \min(M,i\cdot (k+1)-1), \quad \forall \; 1 \le i \le M, 1 \le k \le \left\lfloor \frac{M}{i} \right\rfloor$
We can rewrite the given expression as: $$ \begin{aligned} & \sum_{i=1}^M{\text{freq}_i\cdot \sum_{k=1}^{\left\lfloor \frac{M}{i} \right\rfloor}{k \cdot \sum_{j = l_{i,k}}^{r_{i,k}}\text{freq}_j}} + \sum_{i=1}^M\left(\begin{array}{cc} \text{freq}_i \\ 2 \\ \end{array}\right) \\[6pt] =\; & \sum_{i=1}^M{\text{freq}_i\cdot \sum_{k=1}^{\left\lfloor \frac{M}{i} \right\rfloor}{k \cdot \left(\text{pre}_{r_{i,k}} - \text{pre}_{l_{i,k}-1}\right)}} + \sum_{i=1}^M\left(\begin{array}{cc} \text{freq}_i \\ 2 \\ \end{array}\right) \end{aligned} $$ which can be computed in the given time limit as $\displaystyle \sum_{i=1}^M{\left\lfloor \frac{M}{i} \right\rfloor} = O(M \log M)$.

Time Complexity: $O(N + M\log M)$
Code (C++)
AtCoder - Divisible Substring
Solution
Formally, we have to count the number of pairs $(l,r)$ such that:
- $0 \le l \le r < N$
- The substring $S_l S_{l+1} \ldots S_{r}$ evaluated as an integer is divisible by $P$.
Let us define:
- $\displaystyle \text{suf}_i = \sum_{j=i}^{N-1}\left(S_j \cdot 10^{N-1-j}\right)$: the string $S_i S_{i+1}\ldots S_{N-1}$ evaluated as an integer, $\quad \forall \; 0 \le i < N$.
We can build the $\text{suf}$ array using the following relations: $$ \begin{aligned} & \text{suf}_N = 0 \\[6pt] & \text{suf}_i = \text{suf}_{i+1} + S_i \cdot 10^{N-1-i}, \quad \forall \; 0 \le i < N \end{aligned} $$ The substring $S_l S_{l+1} \ldots S_{r}$ evaluated as an integer can be written as: $$\frac{\text{suf}_l - \text{suf}_{r+1}}{10^{N-1-r}}$$ Replacing $r \rightarrow r-1$, we can rewrite both the conditions as:
- $0 \le l < r \le N$
- $\displaystyle \frac{\text{suf}_l - \text{suf}_{r}}{10^{N-r}} \bmod P = 0$
From here, the following two cases arise:
- Case 1: $\gcd(P,10) \neq 1$ or equivalently $P \in \{2,5\}$
  
  FACT: An integer is divisible by $2$ iff it's last digit is divisible by $2$.
  FACT: An integer is divisible by $5$ iff it's last digit is divisible by $5$.
  
  Thus, we can fix each index $i$ such that $S_i \bmod P = 0$ as the last digit and count the substrings ending at $i$ that are divisible by $P$. Formally, the count is given by: $$\sum_{\substack{i=0 \\ S_i \bmod P = 0}}^{N-1}(i+1)$$
- Case 2: $\gcd(P,10) = 1$
  
  We can simplify the second condition as: $$ \begin{aligned} & \frac{\text{suf}_l - \text{suf}_{r}}{10^{N-r}} \bmod P = 0 \\[6pt] \iff & (\text{suf}_l - \text{suf}_{r})\left({10^{N-r}}\right)^{-1} \bmod P = 0 \\[6pt] \iff & (\text{suf}_l - \text{suf}_{r}) \bmod P = 0 \left(\because \gcd(P,10)=1 \Rightarrow \left({10^{N-r}}\right)^{-1} \bmod P \neq 0\right)\\[6pt] \iff & \text{suf}_r \bmod P = \text{suf}_l \bmod P \end{aligned} $$ To count the number of pairs $(l,r)$ satisfying this, we can iterate on $l$ from $N-1$ to $0$ and keep track of the frequencies of $\text{suf}_r \bmod P$ for $l < r \le N$.
Time Complexity: $O(N+P)$
Code (C++)
Codeforces - Star Sky
Solution
Let us define:
- $\displaystyle \text{val}_{t,i,j} = \sum_{\substack{k=1 \\[3pt] 1 \le x_k \le i \\[3pt] 1 \le y_k \le j}}^n{s_{k,t}}$: the total brightness of stars lying in the rectangle defined by $(1,1)$ and $(i,j)$ at moment $t$, $\quad \forall \; 0 \le t \le c, 1 \le i,j \le N$ where $N = 10^2$.
where $s_{k,t}$ denotes the brightness of the $k^{th}$ star at moment $t$, and is equal to $(s_k + t) \bmod (c+1)$.

To efficiently build the $\text{val}$ array, follow the steps:
- Initialize with all zeros.
- For every star $(x_i, y_i, s_i)$, update $\text{val}_{t,x_i,y_i} \gets \text{val}_{t,x_i,y_i} + (s_i+t) \bmod (c+1), \quad \forall \; 0 \le t \le c$
- Replace the $\text{val}$ array with its prefix sum array.
First update $t_i \gets t_i \bmod (c + 1)$, then the total brightness of stars lying in the rectangle defined by $(x_{1i},y_{1i})$ and $(x_{2i},y_{2i})$ at moment $t_i$ is given by: $$\text{pre}_{t_i,x_{2i},y_{2i}} - \text{pre}_{t_i,x_{1i}-1,y_{2i}} - \text{pre}_{t_i,x_{2i},y_{1i}-1} + \text{pre}_{t_i,x_{1i}-1,y_{1i}-1}$$ Time Complexity: $O(c \cdot N^2 + q)$
Code (C++)

AtCoder - Balanced Rectangles

CodeChef - Cherry and Bits
Solution
Let us define:
- $\displaystyle \text{val}_{i,j} = \bigoplus_{\substack{k=1 \\[3pt] x_{1k} \le i \le x_{2k} \\[3pt] y_{1k} \le j \le y_{2k}}}^q1$: the value of $a_{i,j}$ after all $q$ queries assuming that $a_{i,j} = 0$ initially, $\quad \forall \; 1 \le i \le n, 1 \le j \le m$.
To efficiently build the the $\text{val}$ array, we use the technique of Difference Array:
- Initialize with all zeros.
- For every query $x_{1i},y_{1i},x_{2i},y_{2i}$, we update:
  
  $\text{val}_{x_{1i},y_{1i}} \gets \text{val}_{x_{1i},y_{1i}} \oplus 1$
  
  $\text{val}_{x_{1i},y_{2i}+1} \gets \text{val}_{x_{1i},y_{2i}+1} \oplus 1$
  
  $\text{val}_{x_{2i}+1,y_{1i}} \gets \text{val}_{x_{2i}+1,y_{1i}} \oplus 1$
  
  $\text{val}_{x_{2i}+1,y_{2i}+1} \gets \text{val}_{x_{2i}+1,y_{2i}+1} \oplus 1$
- After processing all the queries, replace $\text{val}$ array by its prefix xor array.
After all $q$ queries, the value at cell $(i,j)$ is given by $a_{i,j} \oplus \text{val}_{i,j}$.

Time Complexity: $O(n\cdot m + q)$
Code (C++)