AT_abc260_g [ABC260G] Scalene Triangle Area

有一个 $N \times N$ 的网格，我们称从上往下第 $i$ 行，从左往右第 $j$ 列的格子为 $(i,j)$。 每个格子上至多放有 $1$ 个棋子。 网格的状态由 $N$ 个字符串 $S_i$ 给出： - 当 $S_i$ 的第 $j$ 个字符为 `O` 时，表示 $(i,j)$ 上有 $1$ 个棋子； - 当 $S_i$ 的第 $j$ 个字符为 `X` 时，表示 $(i,j)$ 上没有棋子。 给定整数 $M$。对于放在 $(s,t)$ 的棋子 $P$，定义 $P$ 能“守护”的格子 $(u,v)$ 满足以下所有条件： - $s \le u \le N$ - $t \le v \le N$ - $(u-s) + \frac{(v-t)}{2} < M$ 现在给定 $Q$ 个格子 $(X_i, Y_i)$，请你求出每个格子被多少个棋子守护。

输入按以下格式从标准输入给出。 > $N$ $M$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$ > $Q$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > $\vdots$ > $X_Q$ $Y_Q$

输出 $Q$ 行。 第 $i$ 行输出格子 $(X_i, Y_i)$ 被守护的棋子数量。

### 数据范围 - $N, M, X_i, Y_i, Q$ 为整数 - $1 \le N \le 2000$ - $1 \le M \le 2N$ - $S_i$ 只包含 `O` 和 `X` - $1 \le Q \le 2 \times 10^5$ - $1 \le X_i, Y_i \le N$ ### 样例解释 1 只有 $(1,1)$ 有棋子，该棋子能守护如下用 `#` 表示的格子： ``` #### ##.. .... .... ``` 由 ChatGPT 4.1 翻译