Hints → https://atcoder.jp/contests/arc158/editorial/5987

Let \([L, R]\) denote the \(L\)-th, \((L+1)\)-th, \(\ldots\), \(R\)-th columns, and \(X\in [L,R]\) denote the fact that \(X\) is a square in \([L,R]\). We use similar notations for half-open intervals \([L,R) = \{i\mid L\leq i<R\}\).

Let us write \(x_i = x_{1,i}\), \(y_i = x_{2,i}\) for simplicity.

For \(1\leq i \leq N\) and \(X\in [1, i]\), let us define \(a_{i, X}\), \(b_{i, X}\) as follows:

\[a_{i, X} = f\bigl((1,i), X),\quad b_{i, X} = f\bigl((2,i), X).\]

Let \(S_i\) be the multiset of pairs of integers defined as \(S_i = \bigl\{(a_{i,X},b_{i,X})\mid X \in [1, i]\bigr\}\). The answer \(\sum_{X,Y}f(X,Y)\) can be found by computing \(\sum_{(a,b)\in S_i}(a+b)\) for each \(i\), which corresponds to finding the sum over the pairs \((X,Y)\) such that the greater of their column numbers is \(i\). Let us consider how to do this.

By division into cases according to whether the two squares in the \(i\)-th column is in the path, we can see that the following hold for \(X\in [1,i-1]\):

\[a_{i,X} = \min\bigl(a_{i-1,X} + x_i, b_{i-1,X} + x_i+y_i\bigr),\qquad b_{i,X} = \min\bigl(a_{i-1,X} + x_i + y_i, b_{i-1,X} + y_i\bigr).\]

Thus, if \(S_i\) is the multiset of pairs of integers defined as \(S_i = \bigl\{(a_{i,X},b_{i,X})\mid X \in [1, i]\bigr\}\), we have:

\[S_{i} = \bigl\{ \min\bigl(a + x_i, b + x_i+y_i\bigr),\min\bigl(a + x_i + y_i, b + y_i\bigr)\mid (a,b) \in S_{i-1}\bigr\} \cup \{(x_i,x_i+y_i), (x_i+y_i,y_i)\}.\]

From case-by-case analysis, the pair \(\bigl(\min\bigl(a + x_i, b + x_i+y_i\bigr),\min\bigl(a + x_i + y_i, b + y_i\bigr)\bigr)\) is equal to the following:

\[\begin{cases} (a+x_i,a+x_i+y_i) & (a-b < -x_i)\\ (a+x_i,b+y_i) & (-x_i\leq a-b \leq y_i)\\ (b+x_i+y_i,b+y_i) & (y_i < a-b). \end{cases} \]

Note that the formula depends on \(a-b\), and we are interested in \(a+b\), and consider \(T_i = \{(a-b,a+b)\mid (a,b)\in S_i\}\) instead of \(S_i\), then the element of \(T_{i}\) for \((a,b)\in T_{i-1}\) is:

\[\begin{cases} (-y_i,b+a+2x_i+y_i) & (a < -x_i)\\ (a+x_i-y_i, b+x_i+y_i) & (-x_i\leq a \leq y_i)\\ (x_i,b-a+x_i+2y_i) & (y_i < a). \end{cases} \]

For our objective, it is enough to find the difference between \(\sum_{(a,b)\in T_{i-1}} b\) and \(\sum_{(a,b)\in T_i} b\), which can be done by maintaining the number of elements of \(T_i\) for each \(a\) using a suitable data structure. We can, for example, use std::map in C++ to solve the problem in \(O(N\log N)\) time. It is also possible to use std::deque to solve it in \(O(N)\) time since we only have to retrieve the minimum and maximum values and insert elements.

• Sample submission: https://atcoder.jp/contests/arc158/submissions/39554314

(Japanese version has some more information.)