3863. [USACO23 Jan Silver] Following Directions

【题目描述】

约翰的农场可以看作一个 $(N+1)×(N+1)$ 的方格矩阵。

矩阵行从上到下编号 $1 \sim N+1$，列从左到右编号 $1 \sim N+1$。

第 $i$ 行第 $j$ 列的方格表示为 $(i,j)$。

满足 $1≤i,j≤N$ 的每个方格 $(i,j)$中都居住着一头奶牛，并且每个这样的方格中都有一个向右或向下的路标。

此外，除了 方格$(N+1,N+1)$ 之外，满足 $i=N+1$ 或 $j=N+1$ 的每个方格 $(i,j)$ 中都有一桶牛饲料，饲料成本为 $c_{i,j}$。

也就是说，每当有一头奶牛来到方格 $(i,j)$ 处吃牛饲料，约翰就需要付出 $c_i$ 的成本。

每头奶牛每天只吃一顿饭，用餐时间在晚上。

每天晚餐时间，约翰都会敲响晚餐铃，奶牛们就会遵循路标指示不断前进，直到到达有牛饲料的方格，奶牛就会停下来进食。

所有奶牛在吃完饲料后，都会回到自己的住所休息。

为了维持预算，约翰想知道每天喂养所有奶牛的总成本。

然而，每天开始晚餐前，都会有一个单元格 $(i,j)$ 中的奶牛翻转其所在方格的路标方向（向右变向下，向下变向右）。

注意，每一天的路标翻转都会对后续天产生影响。

路标方向一旦改变，在接下来的日子里，除非在某一天它又被奶牛翻转回来，否则，它不会自己翻转回来。

一共有 $Q$ 天时间，给定每天翻转路标的单元格坐标，请你计算初始总成本以及每天的实际总成本。

【输入格式】

第一行包含整数 $N$。

接下来 $N+1$ 行，包含路标的初始方向和每桶饲料的成本：

   前 $N$ 行：第 $i$ 行包含一个长度为 $N$ 的由 $R$ 和 $D$ 组成字符串，其中的第 $j$ 个字符表示方格 $(i,j)$ 的路标方向（$R$ 表示向右，$D$ 表示向下），紧接着是一个整数 $C_{i,N+1}$ 表示方格 $(i,N+1)$ 的饲料成本。

   第 $N+1$ 行：包含 $N$ 个整数 $C_{N+1,1},C_{N+1,2},…,C_{N+1,N}$ ，表示方格 $(N+1,j)$ 的饲料成本。

接下来一行包含整数 $Q$。

接下来 $Q$ 行，其中第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 天晚饭前翻转路标的单元格坐标为 $(a_i,b_i)$。

【输出格式】

共 $Q+1$ 行。

第一行输出初始总成本，即没有任何翻转的情况下每天的晚餐总成本。

接下来 $Q$ 行，其中第 $i$ 行输出第 $i$ 天的实际晚餐总成本。

【样例1输入】

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

【样例1输出】

602
701
602
701
1501

【样例2】

点击下载样例2

【样例1说明】

初始时，方格 $(1,1)$ 和 $(1,2)$ 的奶牛饲养成本均为 $1$，方格 $(2,1)$ 的奶牛饲养成本为 $100$，方格 $(2,2)$ 的奶牛饲养成本为 $500$，总成本为 $602$。

第一次翻转后，方格 $(1,1)$ 处的路标方向从 $R$ 变为 $D$，此时方格 $(1,1)$ 处的奶牛饲养成本变为 $100$，其余保持不变，所以总成本变为 $701$。

第二次翻转后，矩阵变回初始状态，总成本为 $602$。

第三次翻转后，矩阵变为第一次翻转后状态，总成本为 $701$。

第四次翻转后，方格 $(1,1)$ 和 $(2,1)$ 的奶牛饲养成本均变为 $500$，总成本为 $1501$。

【数据规模与约定】

测试点 $2-4：1≤N,Q≤50$;

测试点 $5-7：1≤N,Q≤250$;

测试点 $2-10$：每个单元格中的初始方向以及查询都是随机生成的。

对于 $100\%$ 的数据，$1≤N≤1500,1≤c_i,j≤500,1≤Q≤1500,1≤a_i,b_i≤N$。