#P13084. [NOISG 2017] I want to be the very best too! / 宝可梦大师
[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 和宝可梦生活在一个可以用 行 列的网格表示的世界里。其中左上角的网格为 ,右下角的网格为 。小 P 每次只能从一个网格移动到与其相邻的另一个网格。
每一个网格中都有一个宝可梦训练家。小 P 必须与之战斗才能通过这一个网格并获得该宝可梦训练家的宝可梦。
每个宝可梦训练家都有自己的等级。我们不妨认为所有宝可梦训练家的等级都是不同的(这样方便知道每一场战斗的获胜者)。其中,网格 中的训练家的等级为 ,并用种类为 的宝可梦进行战斗。
让事情变得更加困难的是,宝可梦训练家们有时会改变他们的宝可梦的种类。于是,小 P 想提前规划好他的出发时间。因此,小 P 会随时询问你,如果他现在从 出发,并且只能击败等级小于或等于 的宝可梦训练家,那么他最终能拥有多少种宝可梦。
注意,如果他不能打败一个网格中的宝可梦训练家,他就不能穿过该网格。
输入格式
第一行三个整数 ,分别表示世界的行数。
接下来 行,每行 个整数,第 行第 列的整数 表示网格 中的训练家的等级。
接下来 行,每行 个整数,第 行第 列的整数 表示网格 中的训练家的宝可梦的种类。
最后 行,每行四个整数。第一个整数为 ,如果 ,则其后三个整数 ,代表 处的训练师将宝可梦的种类更换为了 ;如果 ,则其后三个整数 ,代表小 P 询问你,如果他现在从 出发,并且只能击败等级小于或等于 的宝可梦训练家,那么他最终能拥有多少种宝可梦。
输出格式
对于小 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 只能通过击败等级分别为 的宝可梦训练家来捕捉种类为 和 的宝可梦。
对于第二次询问,小 P 可以捕捉到所有种类的宝可梦,因为他可以击败除 级之外的所有宝可梦训练家。
对于第三次询问,小 P 无法打败出发的位置处的宝可梦训练家,因此他无法去任何地方,也无法抓住任何种类的宝可梦。
对于第四次询问,小 P 可以捕捉到 种类型的宝可梦,因为 处的训练师现在使用的是种类为 的宝可梦。
数据范围
请注意本题时限为 秒。
本题采用 捆绑测试。
分值 | 特殊性质 | |||
---|---|---|---|---|
处的训练家的等级为 | ||||
无 | ||||
处的训练家的等级为 | ||||
无 |
对于所有数据,保证 ,,,。