U247356 [绍兴一中 NOIP 模拟赛] 积木大赛（block）

[绍兴一中 NOIP 模拟赛]积木大赛（block）T3 ------------ 1s 512MB

一年一度的积木大赛正在举办，一共有 $q$ 位选手参加，每位选手都有自己的任务。 每位选手都在平面直角坐标系上有一座相同的、长为 $n$、高为 $m$ 的积木宝塔，相同字母的联通块为同一块积木，覆盖了以 $(x − 1, y − 1)$ 和 $(x, y)$ 为对顶点的正方形的积木的字母为 $a_{x,y}$，质量为 $b_{x,y}$。 现在第 $i$ 位选手要移动覆盖了 $(x_i − 0.5, y_i − 0.5)$ 的积木，要移动一块积木，必须要移动所有压在这块积木上面的积木。 对于每位选手，求出他要移动多少质量的积木。

从文件 $block.in$ 中读入数据。 第一行三个正整数 $n, m, q$。 接下来 $n$ 行，第 $i$ 行 $m$ 个字符 $a_{1,i}, a_{2,i}, · · · , a_{m,i}$。 接下来 $n$ 行，第 $i$ 行 $m$ 个正整数 $b_{1,i}, b_{2,i}, · · · , b_{m,i}$。 接下来 $q$ 行，第 $i$ 行两个正整数 $y_i, x_i$。

输出到文件 $block.out$ 中。 共 $q$ 行，第 $i$ 行一个正整数表示第 $i$ 位选手要移动的积木的质量。

【测试点约束】 $• 1 ≤ m ≤ n ≤ 10^5 • 1 ≤ nm, q ≤ 10^5 • a_{i,j}$ 是大写字母。 $• 1 ≤ b_{i,j} ≤ 10^4$ **本题使用捆绑测试。** | 测试包编号 | $nm\le$ | $q\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1000$ | $1000$ | | $19$ | | $2$ | $10^5$ | $20$ | | $12$ | | $3$ | $10^5$ | $10^5$ | $AB(2000)$ | $9$ | | $4$ | $10^5$ | $10^5$ | $AB(8000)$ | $7$ | | $5$ | $10^5$ | $10^5$ | $A$ | $23$ | | $6$ | $5\times10^4$ | $10^5$ | | $19$ | | $7$ | $10^5$ | $10^5$ | | $11$ | $A：$ 每个连通块恰好是一个矩形。 $B(x)：$ 联通块数量 $≤ x$。