4322: 「APIO2017」斑斓之地
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
在很久以前的黄金时代，澳大利亚的土地是矩形的，它可以被划分成 $R$ 行 $C$ 列的网格状，行的编号从北到南依次为 $1$ 到 $R$ ，列的编号从西到东依次为 $1$ 到 $C$，$(r,c)$ 表示第 $r$ 行第 $c$ 列的土地。一天，伟大的彩虹蛇从 $(s_r,s_c)$ 出发在澳大利亚的土地上移动，彩虹蛇连续进行了 $M$ 次移动，每次它会向正北 (`N`)、正南 (`S`)、正东 (`E`) 或正西 (`W`) 方向移动一格，其经过的所有的格子（包括起点和终点）都会变成河流。保证在任一时刻，彩虹蛇都不会离开这片 $R$ 行 $C$ 列的矩形土地。
数百万年之后，你想购买一块矩形区域纪念伟大的彩虹蛇。你想给所购买矩形区域内每一块不是河流的格子都染上颜色，要求相邻的格子颜色必须相同，两个格子相邻当且仅当两个格子有一条公共边，你所购买区域之外的格子无须染色。
现在给出彩虹蛇 $M$ 次移动的方向，你有 $Q$ 个购买矩形区域的方案，问每个方案最多能够将土地染上多少种不同的颜色。
输入
第一行：四个整数 $R$，$C$，$M$ 和 $Q$；
第二行：两个整数 $s_r$ 和 $s_c$；
第三行: 一个包含 $M$ 个字符的字符串 $S$，每个字符是 `N`、`S`、`E`、`W` 之一（如果 $M=0$ 则此行留空）；
第四到 $Q+3$ 行: 每行四个整数 $a_r,a_c,b_r$ 和 $b_c$，表示你购买的土地范围，左上角是 $(a_r,a_c)$，右下角是 $(b_r,b_c)$。
输出
对于每个询问做出回答，输出最多能够将土地染上多少种不同的颜色。
样例输入 复制
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3样例输出 复制
0
2
1
3提示
数据范围：对于所有测试数据，$0\le M\le 10^5$，并且 $R,C,Q\ge 1$，对于每个购买矩形土地的方案，都有 $1 \le a_r \le b_r \le R, 1 \le a_c \le b_c \le C$。 详细子任务分值及附加条件如下表。 |子任务编号|分值|$R$|$C$|$Q$| |:-:|:-:|:-:|:-:|:-:| |$1$|$11$|$R\le 50$|$C\le 50$|$Q\le 1000$| |$2$|$12$|$R=2$|$C\le 2\times 10^5$|$Q\le 10^5$| |$3$|$24$|$R\le 2\times 10^5$|$C\le 2\times 10^5$|$Q=1$| |$4$|$27$|$R\le 1000$|$C\le 1000$|$Q\le 10^5$| |$5$|$26$|$R\le 2\times 10^5$|$C\le 2\times 10^5$|$Q\le 10^5$|