#P18372. Frequency Function
Frequency Function
Frequency Function
定义作用于长度为 的整数序列 的函数 。序列中的每个数都在 内。函数返回序列 ,其中 表示数值 在序列 中出现的次数。
这里的下标 从1到 ,所以 不统计数值0的出现次数。
定义 的 次复合:
$$f^k(a)= \begin{cases} a,&k=0,\\ f\bigl(f^{k-1}(a)\bigr),&k>0. \end{cases}$$给定初始序列 ,请依次处理以下两种操作:
1 v x:将原序列中的 改为 。2 k v:输出当前原序列经过 次函数变换后,所得序列的第 个元素,即 。
查询不修改原序列。特别地, 时查询的就是当前 。
输入格式
第一行包含两个整数 ,表示序列长度和操作数。
第二行包含 个整数 。
接下来 行,每行按上述格式描述一种操作。保证至少有一条第二种操作。
输出格式
每条第二种操作输出一行一个整数,表示对应查询的答案。
数据范围
- ;
- ;
- ;
- 两类操作均满足 ;
- 第一类操作满足 ;
- 第二类操作满足 。
输入只有一组数据。
样例输入 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
样例说明
考虑最后一次查询,此时:
- ;
- ;
- 。
所以该次查询的答案是2。