#P13084. [NOISG 2017] I want to be the very best too! / 宝可梦大师

    ID: 12715 Type: RemoteJudge 5000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2017NOISG(新加坡)

[NOISG 2017] I want to be the very best too! / 宝可梦大师

题目背景

译自 NOISG 2017 E.I want to be the very best too! (Pokémon Master)


看到小智成功成为最优秀的人后,小 P 也想追随他的脚步,成为最出色的人!

为了做到这一点,他想抓住种类尽可能多的宝可梦,以填满他的宝可梦图鉴并成为最出色的人。

然而,还有许多其他的宝可梦训练家挡在他面前,他必须打败他们,才能实现他的目标。

题目描述

小 P 和宝可梦生活在一个可以用 RRCC 列的网格表示的世界里。其中左上角的网格为 (1,1)(1,1),右下角的网格为 (C,R)(C,R)。小 P 每次只能从一个网格移动到与其相邻的另一个网格。

每一个网格中都有一个宝可梦训练家。小 P 必须与之战斗才能通过这一个网格并获得该宝可梦训练家的宝可梦。

每个宝可梦训练家都有自己的等级。我们不妨认为所有宝可梦训练家的等级都是不同的(这样方便知道每一场战斗的获胜者)。其中,网格 (j,i)(j,i) 中的训练家的等级为 Li,jL_{i,j},并用种类为 Pi,jP_{i,j} 的宝可梦进行战斗。

让事情变得更加困难的是,宝可梦训练家们有时会改变他们的宝可梦的种类。于是,小 P 想提前规划好他的出发时间。因此,小 P 会随时询问你,如果他现在从 (Xq,Yq)(X_q,Y_q) 出发,并且只能击败等级小于或等于 LqL_q 的宝可梦训练家,那么他最终能拥有多少种宝可梦。

注意,如果他不能打败一个网格中的宝可梦训练家,他就不能穿过该网格。

输入格式

第一行三个整数 R,C,QR,C,Q,分别表示世界的行数。

接下来 RR 行,每行 CC 个整数,第 ii 行第 jj 列的整数 Li,jL_{i,j} 表示网格 (j,i)(j,i) 中的训练家的等级。

接下来 RR 行,每行 CC 个整数,第 ii 行第 jj 列的整数 Pi,jP_{i,j} 表示网格 (j,i)(j,i) 中的训练家的宝可梦的种类。

最后 QQ 行,每行四个整数。第一个整数为 opop,如果 op=1op=1,则其后三个整数 Xq,Yq,PqX_q,Y_q,P_q,代表 (Xq,Yq)(X_q,Y_q) 处的训练师将宝可梦的种类更换为了 PqP_q;如果 op=2op=2,则其后三个整数 Xq,Yq,LqX_q,Y_q,L_q,代表小 P 询问你,如果他现在从 (Xq,Yq)(X_q,Y_q) 出发,并且只能击败等级小于或等于 LqL_q 的宝可梦训练家,那么他最终能拥有多少种宝可梦。

输出格式

对于小 P 的每次询问,输出一行一个整数,即他最终能拥有的宝可梦种类数。

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
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 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
3 3 5
1 4 3
11 2 7
5 10 6
6 3 3
4 6 4
9 4 9
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 7
2 2 1 4
2
4
0
3

提示

样例 4 解释

对于第一次询问,小 P 只能通过击败等级分别为 1,2,3,41,2,3,4 的宝可梦训练家来捕捉种类为 3366 的宝可梦。

对于第二次询问,小 P 可以捕捉到所有种类的宝可梦,因为他可以击败除 1111 级之外的所有宝可梦训练家。

对于第三次询问,小 P 无法打败出发的位置处的宝可梦训练家,因此他无法去任何地方,也无法抓住任何种类的宝可梦。

对于第四次询问,小 P 可以捕捉到 33 种类型的宝可梦,因为 (2,2)(2,2) 处的训练师现在使用的是种类为 77 的宝可梦。

数据范围

请注意本题时限为 55 秒。

本题采用 Subtask\text{Subtask} 捆绑测试。

Subtask\text{Subtask} 分值 RR QQ 特殊性质
11 1111 =1=1 1000\le1000 (X,1)(X,1) 处的训练家的等级为 XX
22 1616 5×104\le5\times10^4 10\le10
33 2020 105\le10^5 1Pi,j,Pq21\le P_{i,j},P_q\le2
44 2424 =1=1 (X,1)(X,1) 处的训练家的等级为 XX
55 2929 5×104\le5\times10^4

对于所有数据,保证 1R×C5×1041\le R\times C\le5\times10^41Q1051\le Q\le 10^51Li,j,Lq1091\le L_{i,j},L_q \le10^91Pi,j,Pq5×1041\le P_{i,j},P_q\le 5\times10^4