5996: 进阶2.5.5 序列操作
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：83
解决：16
题目描述
有由 N 个非负整数组成的序列：a[1], a[2], ..., a[N]，对该序列进行 M 个操作，操作形式：① S X Y，将 a[X] 的值改为 Y；② Q L R D P，求[L, R]区间第 D 位数是 P 的元素个数，L 和 R 是序列的索引，注意：第 1 位是最低位。
输入
第一行都包含两个整数 N 和 M
第二行包含 N 个整数
后面 M 行
若类型为 S 则包含一个字母 S 和两个整数 X 和 Y
若类型为 Q 则包含一个字母 Q 和四个整数 L R D P
第二行包含 N 个整数
后面 M 行
若类型为 S 则包含一个字母 S 和两个整数 X 和 Y
若类型为 Q 则包含一个字母 Q 和四个整数 L R D P
输出
对每个Q操作都单独一行输出答案
样例输入 复制
5 7
10 11 12 13 14
Q 1 5 2 1
Q 1 5 1 0
Q 1 5 1 1
Q 1 5 3 0
Q 1 5 3 1
S 1 100
Q 1 5 3 1样例输出 复制
5
1
1
5
0
1提示
1 ≤ N, M ≤ 100 000
0 ≤ a[i] ≤ 2 ^ 31 - 1
1 ≤ X ≤ N
0 ≤ Y ≤ 2 ^ 32 - 1
1 ≤ L ≤ R ≤ N
1 ≤ D ≤ 10
0 ≤ P ≤ 9
0 ≤ a[i] ≤ 2 ^ 31 - 1
1 ≤ X ≤ N
0 ≤ Y ≤ 2 ^ 32 - 1
1 ≤ L ≤ R ≤ N
1 ≤ D ≤ 10
0 ≤ P ≤ 9