1406: 装备合成

题目描述

ygx最近在玩一款游戏，他收集了$k$个装备，编号为$1,2,3,…,k$。每个装备有$n$种属性。每次可以将两个装备合成一个新的装备（原来的两个装备不会消失）。但是合成有可能会失败。如果合成成功，那么新装备的各项属性值是原来的两个装备的对应项属性值的较大值；如果合成失败，那么新装备的各项属性值是原来的两个装备的对应项属性值的较小值。无论是否成功，ygx都会保留合成得到的装备，并将它编号为$m+1$（$m$为合成前ygx已经拥有的装备数量）。

由于ygx的装备实在是太多了，所以他有时想知道编号为$x$的装备的第$y$项属性值是多少。

输入格式

第一行三个正整数$n,k,q$。分别表示属性的数量，ygx初始拥有的装备的数量和ygx的操作数。

接下来$k$行每行$n$个整数，第$i$行的第$j$个整数表示第$i$件装备的第$j$项属性值$a_{ij}$。

接下来$q$行每行描述一个操作：

1 a b表示ygx将编号为$a$和$b$的装备合成了一件新装备且合成成功了。数据保证在这个时间点$a,b$是存在的。

2 a b表示ygx将编号为$a$和$b$的装备合成了一件新装备且合成失败了。数据保证在这个时间点$a,b$是存在的。

3 x y表示ygx想知道编号为$x$的装备的第$y$项属性值。数据保证在这个时间点$x$是存在的。

输出格式

对于每个询问输出一行答案。

样例输入

text 3 3 7 1 6 9 3 5 1 8 7 2 1 1 2 2 4 3 2 5 1 1 6 6 3 5 2 3 4 3 3 7 1

样例输出

text 6 9 1

数据范围

样例解释

第一个操作得到了编号为$4$的装备，属性值分别为$3\ 6\ 9$

第二个操作得到了编号为$5$的装备，属性值分别为$3\ 6\ 2$

第三个操作得到了编号为$6$的装备，属性值分别为$1\ 6\ 2$

约定

对于$30\%$的数据，$n\le100$

对于另外$20\%$的数据，$n\le10^5$，并且保证合成不会失败（即没有操作$2$）

对于另外$30\%$的数据，$n\le10^5$，并且保证$1\le a_{ij}\le2$

对于所有数据，$n\le10^5,\ k\le12,\ q\le10^5,\ 1\le a_{ij}\le10^9$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！