P9014 [USACO23JAN] Following Directions S

题目描述

注：本题时限为 8s，是默认时限的四倍。

Farmer John 有一个正方形的草地，草地被划分为了 $(N + 1) \times (N + 1)(1 \leq N \leq 1500)$ 的格子。设 $(i, j)$ 为从上到下、从左到右第 $i$ 行，第 $j$ 列的格子。每个满足 $1 \leq i, j \leq n$ 的格子 $(i, j)$ 之中都住着一头牛，而且每个这样的格子上都有一个路标指向右或下。除此之外，所有满足 $i = N + 1$ 或 $j = N + 1$ 的格子，除了 $(N + 1, N + 1)$ 都会有一个饲料桶。牛在每个饲料桶进食需要的价格不同；位置 $(i, j)$ 上的桶喂饱一只牛需要价格 $c_{i, j}(1 \leq c_{i, j} \leq 500)$。

每天晚饭时间，Farmer John 摇响晚餐铃时，所有牛都沿着路标的指向前进，直到它们遇到了饲料桶，之后它们会在它们自己遇到的饲料桶那里进食。第二天，所有牛又会回到自己原来的位置。

为了维持预算，Farmer John 想要知道每天喂食需要的价钱。然而，每天晚饭之前，总会有一头牛 $(i, j)$ 翻转它那里的路标（原来向下则变成向右，反之亦然）。被翻转的路标指向将在后面的日子里保持不变，除非它又被进行了翻转。

给出每天被翻转的路标的坐标，请输出每天喂食需要的价格（总共有 $Q$ 天，$1 \leq Q \leq 1500$）。

输入格式

第一行为 $N(1 \leq N \leq 1500)$

接下来的 $N + 1$ 行从上到下输入初始的路标朝向和每个饲料桶的价格 $c_{i, j}$。前 $N$ 行每行包含一个长度为 $N$ 的字符串，其中每个字符只能是 R 或 D（R 表示向右，D 表示向下），之后是一个数，表示价格 $c_{i, N + 1}$，第 $(N + 1)$ 行包含 $N$ 个数，依次表示价格 $c_{N + 1, j}$。

接下来的一行为 $Q(1 \leq Q \leq 1500)$。

之后的 $Q$ 行，每行有两个整数 $i$ 和 $j(1 \leq i, j \leq N$，表示每天被翻转的路标的坐标。

输出格式

共 $Q + 1$ 行：第一行是初始的总价格，之后 $Q$ 行依次是每次被翻转后的总价格。

输入输出样例 1

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

602
701
602
701
1501

说明/提示

样例 1 解释

在第一次翻转之前，喂养在位置 $(1, 1)$ 和 $(1, 2)$ 的牛需要的价格都为 $1$，喂养在 $(2, 1)$ 的牛需要的价格为 $100$，喂养在 $(2, 2)$ 的牛需要的价格为 $500$。总价格为 $602$。第一次翻转后，在 $(1, 1)$ 处的路标由 R 变为 D，此时在位置 $(1, 1)$ 的牛喂养的价格变为 $100$（其它牛的价格没有变化），所以总价为 $701$。第二次和第三次翻转都在来回翻转同一个路标。第四次翻转后，在位置 $(1, 1)$ 和位置 $(2, 1)$ 的牛喂养的价格变为 $500$，总价变为 $1501$。

• 测试点 $2 - 4$ 中：$1 \leq N, Q \leq 50$。

• 测试点 $5 - 7$ 中：$1 \leq N, Q \leq 250$。

• 测试点 $2 - 10$ 中：每个路标初始朝向以及被翻转的路标为随机生成。

• 测试点 $11 - 15$ 中：无特殊条件。