AtCoder Beginner Contest 269 F問題 Numbered Checker

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

2重添字数列 $H=\left(H_{i,j} \right)_{\substack{1 \leq i \leq N \\ 1 \leq j \leq M}}$ を

$H_{i,j}=\begin{cases} (i-1)M+j & (i+j: {\rm even}) \\ 0 & (i+j: {\rm odd}) \end{cases}$

次の $Q$ 個の問に答えよ.

以下を求めよ.

$\displaystyle \sum_{\substack{A_q \leq i \leq B_i \\ C_q \leq j \leq D_q}} H_{i,j}$

制約

$1 \leq N,M \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq A_q \leq B_q \leq N$
$1 \leq C_q \leq D_q \leq M$

解法1

$\displaystyle T(a,b,c,d):=\sum_{\substack{a \leq i \leq b \\ c \leq j \leq d}} H_{i,j}$

とする. このとき, $0 \leq b \leq N, 0 \leq d \leq M$ に対して, $K(b,d)$ を

$\displaystyle K(b,d):=\sum_{\substack{1 \leq i \leq b \\ 1 \leq j \leq d}} H_{i,j}$

とすると,

$T(a,b,c,d)=K(b,d)-K(a-1,d)-K(b,c-1)+K(a-1,c-1)$

であるから, $K(\bullet, \bullet)$ を高速に求められれば良い.

解法2

ここで, $S(d,a,n)$ を初項 $a+d$ , 交差 $d$ , 項数 $n$ の等差数列の和とする. つまり,

$\displaystyle S(d,a,n):=\sum_{i=1}^n (di+a)=\dfrac{n(2a+(n+1)d)}{2}$

である.

まず, 2つの引数が共に偶数である場合を求める. $K(2s, 2t)$ を求めることにする.

$\begin{align} K(2s,2t) &=\sum_{\substack{1 \leq i \leq 2s \\ 1 \leq j \leq 2t}} H_{i,j} \\ &=\sum_{\substack{1 \leq i \leq s \\ 1 \leq j \leq t}} (H_{2i-1,2j-1}+H_{2i-1, 2j}+H_{2i, 2j-1}, H_{2i, 2j}) \\ &=\sum_{\substack{1 \leq i \leq s \\ 1 \leq j \leq t}} ( ( (2i-1-1) M+(2j-1))+( (2i-1)M+2j) ) \\ &=\sum_{\substack{1 \leq i \leq s \\ 1 \leq j \leq t}} ( (4i-3) M+(4j-1)) \\ &=\sum_{1 \leq i \leq s} ( (4i-3)Mt+2t(t+1)-t) \\ &=t \sum_{1 \leq i \leq s} (4M i+(1+2t-3M) ) \\ &=t S(4M, 1+2t-3M, s) \end{align}$

である. ちなみに, 計算を進めると,

$K(2s, 2t)=\dfrac{1}{2} \times \dfrac{(2s)(2t)}{2} (H_{1,1}+H_{2s, 2t})$

であることもわかる.

次に, $K(2s, 2t-1)$ の場合を求める. このとき, $2s, 2t-2$ は共に偶数なので, 上の場合を利用して

$\displaystyle \begin{align} K(2s, 2t-1) &=K(2s, 2t-2)+\sum_{1 \leq i \leq 2s} H_{i,2t-1} \\ &=K(2s, 2t-2)+\sum_{1 \leq i \leq s} H_{2i-1,2t-1} \\ &=K(2s, 2t-2)+\sum_{1 \leq i \leq s} ( (2i-1-1)M+(2t-1) ) \\ &=K(2s, 2t-2)+\sum_{1 \leq i \leq s} (2Mi+(2t-2M-1))\\ &=K(2s, 2t-2)+S(2M, 2t-2M-1, s) \\ \end{align}$

である.

同様に, $K(2s-1, 2t)$ の場合も

$\displaystyle \begin{align} K(2s-1, 2t) &=K(2s-2, 2t)+\sum_{1 \leq j \leq 2t} H_{2s-1,j} \\ &=K(2s-2, 2t)+\sum_{1 \leq j \leq t} H_{2s-1, 2j-1} \\ &=K(2s-2, 2t)+\sum_{1 \leq j \leq t} ( (2s-1-1)M+(2j-1) ) \\ &=K(2s-2, 2t)+\sum_{1 \leq j \leq t} (2j +2M(s-1)-1)\\ &=K(2s-2, 2t)+S(2, 2M(s-1)-1, t) \end{align}$

である.

最後に, $K(2s-1, 2t-1)$ の場合を求める.

$\displaystyle \begin{align} &\phantom{=}K(2s-1, 2t-1)\\ &=K(2s-2, 2t-2)+\sum_{1 \leq i \leq 2s-2} H_{i, 2t-1}+\sum_{1 \leq j \leq 2t-2} H_{2s-1,j}+H_{2s-1, 2t-1}\\ &=K(2s-2, 2t-2)+\sum_{1 \leq i \leq s-1} H_{2i-1, 2t-1}+\sum_{1 \leq j \leq t-1} H_{2s-1, 2j-1}+H_{2s-1, 2t-1}\\ &=K(2s-2, 2t-2)+\sum_{1 \leq i \leq s-1} ( (2i-1-1)M+(2t-1) ) \\ &\quad +\sum_{1 \leq j \leq t-1} ( (2s-1-1)+(2j-1))+H_{2s-1, 2t-1}\\ &=K(2s-2, 2t-2)+\sum_{1 \leq i \leq s-1} (2Mi+(-2M+2t-1) ) \\ &\quad +\sum_{1 \leq j \leq t-1} ( 2j+(2M(s-1)-1) )+H_{2s-1, 2t-1}\\ &=K(2s-2, 2t-2)+S(2M, -2M+2t-1,s-1) \\ &\quad +S(2, 2M(s-1)-1, t-1)+H_{2s-1, 2t-1} \end{align}$