#P9580. 雨雪霏霏

    ID: 6196 传统题 5000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-Kruskal 重构树普通并查集树上倍增子树转区间带修改莫队时间维度移动

雨雪霏霏

题目描述

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

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

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

输入格式

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

接下来 RR 行,每行 CC 个正整数,其中第 ii 行第 jj 个数表示 Li,jL_{i,j}。

接下来 RR 行,每行 CC 个正整数,其中第 ii 行第 jj 个数表示 Ci,jC_{i,j}。

接下来 QQ 行,每行 44 个整数:

  • 如果第一个数是 11,则接下来三个数依次为 x,y,cx, y, c,表示将 (x,y)(x, y) 的颜色改成 cc。
  • 如果第一个数是 22,则接下来三个数依次为 x,y,Lx, y, L,表示一个下雨的日子,也即询问。

输出格式

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

样例

样例 1

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
1
2
0
1

样例 2

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
2
4
0
3

样例 3

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
1
2
0
2

数据范围

  • 子任务 11,分值 1111 分,保证 R=1,Q≤103R = 1, Q \le 10^3,位置 (X,1)(X, 1) 的海拔为 XX。
  • 子任务 22,分值 1616 分,保证 Q≤10Q \le 10。
  • 子任务 33,分值 2020 分,保证 1≤Ci,j,c≤21 \le C_{i,j} , c \le 2。
  • 子任务 44,分值 2424 分,保证 R=1R = 1,位置 (X,1)(X, 1) 的海拔为 XX。
  • 子任务 55,分值 2929 分,无特殊限制。

对所有数据,1≤R×C≤5×1041\le R\times C\le 5\times 10^4,1≤Q≤1051\le Q\le 10^5,1≤Ci,j,c≤5×1041\le C_{i,j},c\le 5\times 10^4,1≤Li,j≤1091\le L_{i,j}\le 10^9,保证所有格子海拔互不相同。