2020/10/10に行われたAtCoder HHKBプログラミングコンテスト 2020のD問題Squaresをコンテスト時間中に解けなくて悔しい思いをしたので、終わってからもう一度解き方を整理してみました。
初めてのQiita投稿です。Markdown書くのも初めて！
見出しに数式って使えないのかな？
公式解説とはちょっと違うと思います。具体的には
$X_2$: 長さ $A$の区間と長さ$B$の区間を長さ$N$の区間に詰めた時に重なる方法の数。
ここを余事象を使わずに直接求めています。
数式使ってゴリゴリ押したいタイプ向けかなあ？
方針
$T \le 10^5$ 個のクエリに答えなければならないので、1個あたりのクエリは遅くても $O\left(\log{N}\right)$ 、まあ多分 $O\left(1\right)$ で解くんだろうなとわかります。
→数学問題だね！
青い正方形と赤い正方形が重ならない置き方の数を直接数えるのは大変そうなので、余事象、つまり
青い正方形と赤い正方形が重なる置き方の数（$C$とする）を求め、全事象の数から引いて答えを出します。
全事象（すべての青い正方形と赤い正方形の置き方の数）は $(N - A + 1)^{2} \cdot (N - B + 1)^{2}$ なので、答え $ans$ は
$$
\textrm{ans} = (N - A + 1)^{2} \cdot (N - B + 1)^{2} - C
$$
と書けます。
余事象Cを求める
青い正方形（辺の長さ$A$）の左下の座標 $(x, y)$ を固定して考えます。
赤い正方形の$x$座標が青い正方形の$x$座標と重なるような、赤い正方形の$x$座標の選び方の数 $f(x)$ は
$$
f(x) = \min(N, x + A + B - 1) - \max(0, x + 1 - B) - B + 1
$$
となります。
同様に、赤い正方形の$y$座標が青い正方形の$y$座標と重なるような、赤い正方形の$y$座標の選び方は $f(y)$ となります。
つまり、青い正方形の位置を固定した場合、赤い正方形が青い正方形に重なるような位置の選び方は $f(x) \cdot f(y)$ です。
これをすべての$x$と$y$の組み合わせについて足してやれば良いので、
$$
C
= \sum_{x = 0}^{N - A}\sum_{y = 0}^{N - A}{f(x) \cdot f(y)}
= \sum_{x = 0}^{N - A}{f(x)}\sum_{y = 0}^{N - A}{f(y)}
= \left(\sum_{x = 0}^{N - A}{f(x)}\right)^{2}
$$
となります。
Σf(x)を求める
\begin{eqnarray*}
\sum_{x = 0}^{N - A}{f(x)}
& = & \sum_{x = 0}^{N - A}{\left(\min\left(N, x + A + B - 1\right) - \max\left(0, x + 1 - B\right) - B + 1\right)}\\
& = & \underbrace{ \sum_{x = 0}^{N - A}{\min\left(N, x + A + B - 1\right)} }_{F\textrm{とおく}}
- \underbrace{\sum_{x = 0}^{N - A}{\max\left(0, x + 1 - B\right)}}_{G\textrm{とおく}}
- \underbrace{\sum_{x = 0}^{N - A}{\left(B - 1\right)}}_{H\textrm{とおく}} \\
& = & F - G - H
\end{eqnarray*}
と書けます。
Fを求める
\begin{equation*}
\min\left(N, x + A + B - 1\right) =
\begin{cases}
x + A + B - 1 & \left(x \le N - A - B + 1 \text{ のとき}\right)\\
N & \left(x \ge N - A - B + 2\text{ のとき}\right)
\end{cases}
\end{equation*}
となります。
Case 1-1: N - A - B + 2 ≦ 0 の場合
この場合、 $0 \le x \le N - A$ の範囲の $x$ について、 $x \ge N - A - B + 2$ を常に満たします。そのため、
$$
F = \sum_{x = 0}^{N - A}{N} = (N - A + 1) \cdot N
$$
です。
Case 1-2: N - A - B + 2 > 0 の場合
$B \ge 2$ のとき、 $0 \le N - A - B + 1$ かつ $N - A - B + 2 \le N - A$ となるので、
\begin{eqnarray*}
F
& = & \sum_{x = 0}^{N - A - B + 1}{(x + A + B - 1)} + \sum_{x = N - A - B + 2}^{N - A}{N}\\
& = & \frac{\left( A + B - 1 + N \right)\cdot \left( N - A - B + 2 \right)}{2}
+ N \cdot (B - 1)
\end{eqnarray*}
です。 $B = 1$ のときは、 $N - A - B + 2 > N + A$ となってしまうため、2項目が要注意ですが、 $N\cdot\left(B - 1\right) = 0$となるので、このままの式で問題ないです。
Gを求める
\begin{equation*}
\max\left(0, x + 1 - B\right) =
\begin{cases}
0 & (x \le B - 2 \text{ のとき})\\
x + 1 - B & (x \ge B - 1 \text{ のとき})
\end{cases}
\end{equation*}
となります。
Case 2-1: N - A - B + 2 ≦ 0の場合
この場合、 $0 \le x \le N - A$ の範囲の$x$について、 $x \le N - A \le B - 2$ なので、 $x \le B - 2$ を常に満たします。
そのため、
$$
G = \sum_{x = 0}^{N - A}{0} = 0
$$
です。
Case 2-2: N - A - B + 2 > 0 の場合}
$B \ge 2$ のとき、 $0 \le B - 2$ かつ $B - 1 \le N - A$ となるので、
\begin{align}
G
& = \sum_{x = 0}^{B - 2}{0} + \sum_{x = B - 1}^{N - A}{(x + 1 - B)}\\
& = \frac{\left( N - A - B + 1 \right)\cdot \left( N - A - B + 2 \right)}{2}
\end{align}
です。$B = 1$ のときも、$G = \sum_{x = 0}^{N - A}{(x + 1 - B)}$ なので、上の式が使えます。
Hを求める
$$
H = (B - 1) \cdot (N - A + 1)
$$
です。
以上から答えを導けます。