4120. 雨(yù)雪霏霏

单点时限: 4.0 sec

内存限制: 512 MB

雨雪国的地图可以抽象成一张 $R\times C$ 的网格,左上角 $(1,1)$,右下角 $(C,R)$。每个格子都涂有一个颜色,位于 $(j,i)$ 的格子颜色为 $C_{i,j}$,海拔为 $L_{i,j}$。

顾名思义,雨雪国是个经常下大雪的国度。当雪降落在格子 $(x,y)$ 时,就会向四联通的格子们蔓延,并蔓延到海拔不超过 $L$ 的格子。所有这些格子上涂有的颜色被混在一起,而小 G 想知道其中有多少种不同的颜色。注意:如果 $(x,y)$ 的海拔超过了 $L$,答案是 0。

为了增加趣味性,小 G 有时还会修改某个格子上的颜色。所有下雪的日子(也就是询问)互不影响。

输入格式

第一行,三个正整数 $R,C,Q$

接下来 $R$ 行,每行 $C$ 个正整数,其中第 $i$ 行第 $j$ 个数表示 $L_{i,j}$

接下来 $R$ 行,每行 $C$ 个正整数,其中第 $i$ 行第 $j$ 个数表示 $C_{i,j}$

接下来 $Q$ 行,每行 $4$ 个整数

  • 如果第一个数是 $1$,则接下来三个数依次为 $x,y,c$,表示将 $(x,y)$ 的颜色改成 $c$
  • 如果第一个数是 $2$,则接下来三个数依次为 $x,y,L$,表示一个下雨的日子,也就是询问

输出格式

对每个询问,输出一行表示答案

样例

Input
1 5 5
1 2 3 4 5
1 1 2 1 2
2 2 1 2
2 1 1 4
2 4 1 3
1 3 1 1
2 3 1 4
Output
1
2
0
1
Input
1 5 5
1 2 3 4 5
3 4 3 2 5
2 3 1 3
2 1 1 5
2 4 1 2
1 4 1 4
2 3 1 5
Output
2
4
0
3
Input
3 3 5
1 4 3
11 2 7
5 10 6
1 1 1
2 1 2
1 2 1
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 2
2 2 1 4
Output
1
2
0
2

提示

子任务 $1$,分值 $11$ 分,保证 $R=1,Q\le 1000$,位置 $(X,1)$ 的海拔为 $X$

子任务 $2$,分值 $16$ 分,保证 $Q\le 10$

子任务 $3$,分值 $20$ 分,保证 $1\le C_{i,j},c\le 2$

子任务 $4$,分值 $24$ 分,保证 $R=1$,位置 $(X,1)$ 的海拔为 $X$

子任务 $5$,分值 $29$ 分,无特殊限制

对所有数据,$1\le R\times C\le 50000,1\le Q\le 10^5$,$1\le C_{i,j},c\le 50000$,$1\le L_{i,j}\le 10^9$,保证所有格子海拔互不相同

13 人解决,113 人已尝试。

22 份提交通过,共有 573 份提交。

8.2 EMB 奖励。

创建: 3 月前.

修改: 2 月前.

最后提交: 3 周,3 天前.

来源: N/A

题目标签