CF418E Tricky Password

为了确保保密性，在“Russian Code Cup”题目开发过程中，题目的访问需要密码保护。 为了选择一个密码，评委会可以生成一个特殊的表格，这个表格有 $n$ 列和无限多行。构造表格的方法如下： 第一行为初始固定值，其余各行按如下规则生成： 在第 $i$ 行第 $p$ 列的位置的数 $a[i][p]$ 等于 $a[i-1][p]$ 在第 $i-1$ 行前 $p$ 个数 $a[i-1][1...p]$ 中出现的次数。 为保证足够的保密等级，评委需要实现以下两种操作： - 将第一行的第 $p$ 个数字替换为 $v$，并据此重建整个表格。 - 查询 $a[x][y]$，该数将作为新密码。 手工执行这些操作十分繁琐，因此评委请求你帮忙编写程序来响应这些请求。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$）——表示表格的列数。 第二行为第一行的 $n$ 个整数，每个数都不少于 $1$ 且不超过 $10^9$。 第三行是一个整数 $m$（$1 \leq m \leq 100000$）——表示请求的数量。 接下来 $m$ 行，每行包含三个整数，描述一次请求： - 如果第一个整数为 $1$，则接下来的两个数为 $v, p$（$1 \leq v \leq 10^9$，$1 \leq p \leq n$）。表示将第一行第 $p$ 列的值改为 $v$，并重建表格。 - 如果第一个整数为 $2$，则接下来的两个数为 $x, y$（$1 \leq x \leq 10^5$，$1 \leq y \leq n$），表示询问 $a[x][y]$ 的值。

对于每个类型为 2 的请求，按顺序输出对应的答案。

由 ChatGPT 5 翻译