Numbered Checker

题目描述

我们有一个有 $N$ 行 $M$ 列的网格。位于从上数第 $i$ 行、从左数第 $j$ 列的方格 $(i,j)$ 上写着整数 $(i-1) \times M + j$。
我们对这个网格执行如下操作。

对于每个满足 $i+j$ 为奇数的方格 $(i,j)$，把该方格上的整数替换为 $0$。

回答关于操作后网格的 $Q$ 个查询。
第 $i$ 个查询如下：

求所有满足下列条件的方格 $(p,q)$ 上所写整数的和，对 $998244353$ 取模。 $A_i \le p \le B_i$。 $C_i \le q \le D_i$。

输入格式

输入以标准输入给出，格式如下： $N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_Q$ $B_Q$ $C_Q$ $D_Q$

输出格式

输出 $Q$ 行。
第 $i$ 行应包含第 $i$ 个查询的答案，形式为一个整数。

5 4
6
1 3 2 4
1 5 1 1
5 5 1 4
4 4 2 2
5 5 4 4
1 5 1 4

28
27
36
14
0
104

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

716070898
240994972
536839100

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

712559605
648737448
540261130

提示

输入中的所有数值均为整数。 $1 \le N,M \le 10^9$ $1 \le Q \le 2 \times 10^5$ $1 \le A_i \le B_i \le N$ $1 \le C_i \le D_i \le M$该输入对应的网格如下所示。
该输入包含六个查询。

第一个查询的答案是 $0+3+0+6+0+8+0+11+0=28$。 第二个查询的答案是 $1+0+9+0+17=27$。 第三个查询的答案是 $17+0+19+0=36$。 第四个查询的答案是 $14$。 第五个查询的答案是 $0$。 第六个查询的答案是 $104$.
对于第一个查询，注意虽然方格 $(10^9,10^9)$ 上写着整数 $10^{18}$，但你应当对 $998244353$ 取模来求其值。

标签: AtCoder|abc269F

来源

AtCoder|abc269F