#P18372. Frequency Function

Frequency Function

Frequency Function

定义作用于长度为 nn 的整数序列 a=(a1,a2,…,an)a=(a_1,a_2,\ldots,a_n) 的函数 ff。序列中的每个数都在 [0,n][0,n] 内。函数返回序列 b=(b1,b2,…,bn)b=(b_1,b_2,\ldots,b_n),其中 bib_i 表示数值 ii 在序列 aa 中出现的次数。

这里的下标 ii 从1到 nn,所以 ff 不统计数值0的出现次数。

定义 ff 的 kk 次复合:

$$f^k(a)= \begin{cases} a,&k=0,\\ f\bigl(f^{k-1}(a)\bigr),&k>0. \end{cases}$$

给定初始序列 aa,请依次处理以下两种操作:

  • 1 v x:将原序列中的 ava_v 改为 xx。
  • 2 k v:输出当前原序列经过 kk 次函数变换后,所得序列的第 vv 个元素,即 fk(a)vf^k(a)_v。

查询不修改原序列。特别地,k=0k=0 时查询的就是当前 ava_v。

输入格式

第一行包含两个整数 n,qn,q,表示序列长度和操作数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 qq 行,每行按上述格式描述一种操作。保证至少有一条第二种操作。

输出格式

每条第二种操作输出一行一个整数,表示对应查询的答案。

数据范围

  • 1≤n≤3000001\le n\le300000;
  • 1≤q≤5000001\le q\le500000;
  • 0≤ai≤n0\le a_i\le n;
  • 两类操作均满足 1≤v≤n1\le v\le n;
  • 第一类操作满足 0≤x≤n0\le x\le n;
  • 第二类操作满足 0≤k≤3000000\le k\le300000。

输入只有一组数据。

样例输入 1

6 6
2 1 2 3 0 3
2 3 2
1 5 2
2 0 2
1 2 3
2 0 2
2 2 3

样例输出 1

1
1
3
2

样例说明

考虑最后一次查询,此时:

  • f0(a)=[2,3,2,3,2,3]f^0(a)=[2,3,2,3,2,3];
  • f1(a)=[0,3,3,0,0,0]f^1(a)=[0,3,3,0,0,0];
  • f2(a)=[0,0,2,0,0,0]f^2(a)=[0,0,2,0,0,0]。

所以该次查询的答案是2。