题解

思路

考虑走完前 $t$ 步后位于第 $t$ 条副对角线上的一个格子，并用 $x$ 表示已经向下走的步数，则向右走的步数是 $t-x$。

做法

这个格子能被某条合法路径经过，当且仅当前缀中已经固定的 D、R 分别不超过 $x$、$t-x$，同时后缀中固定的 D、R 分别不超过剩余的向下、向右步数。将这四个条件再与网格边界合并，就能得到 $x$ 的一个整数可行区间；区间内每个整数恰好对应这条副对角线上的一个可染黑格子。

预处理 $S$ 中 D 和 R 的前缀数量，便可在常数时间求出每个 $t=0,1,\ldots,H+W-2$ 对应区间的左右端点，把所有非空区间长度相加即为答案。判断只使用必要且充分的前后缀条件，因此既不会漏掉可由某条合法路径经过的格子，也不会计入不可能经过的格子。

复杂度

每组数据的时间复杂度为 $O(H+W)$，空间复杂度为 $O(H+W)$。