The theme of this problem is a standard technique for queries involving range addition and counting zeros.

Understanding what to compute

We want the sum of \(i\times j\) over all cells \((i,j)\) that were never affected by even \(1\) operation.

Maintaining the number of operations affecting each cell

Scan the grid from top to bottom while maintaining, for \(1\) row, how many operations affect each cell. Each operation can be represented by the following \(2\) uniform range additions:

1. When entering row \(a_k\), add \(1\) to every entry in the range \(b_k\leq j \leq d_k\).
2. When leaving row \(c_k\), add \(-1\) to every entry in the range \(b_k\leq j \leq d_k\).

Counting zeros with weights

For row \(i\), we want “the sum of the indices \(j\) for which cell \((i,j)\) has an operation count of \(0\).” Since values below \(0\) never appear, we can instead maintain “the minimum operation count among cells \((i,j)\) and the sum of the indices \(j\) attaining that minimum.”

For sequences \(A,W\), define \(f(A,W)=(x,c)\), where

• \(x\) is the minimum of \(A\).
• \(c\) is the sum of \(W_i\) over indices satisfying \(A_i=x\).

We can maintain this information in a segment tree. Using a lazy segment tree additionally supports uniform range additions to \(A\): simply add the update value to \(x\).

In this problem, use \(W=(1,2,\ldots ,N)\). If the query result has \(x=0\), its contribution to the answer is \(c\) multiplied by \(i\). Sum these contributions to obtain the answer. The time complexity is \(O(N+Q\log N)\).

Sample solution

• Nachia, C++