题目描述
对一个长度为 N 的序列 {an}(ai∈[0,216−1]),进行如下两种,共计 M 个操作:
-
A x(x≥0):执行 ai←(ai+x)mod216。
-
Q i:询问 $\#\{k\mid(a_k\;\&\;2^i)>0,1\le k\le N,k\in\mathbb{Z}\}$ 的结果,其中 #A 表示集合 A 的大小。
其中 & 运算符为相当于 C/C++ 中的 & 或 Pascal 中的 and。
给定初始序列和操作序列,请你模拟操作过程,并计算所有 Q 操作的相应的结果的和。
输入格式
输入文件的第一行包含两个以空格分隔的整数,分别代表 N,M。
接下来的 N 行每行包含一个整数,代表初始序列。
接下来的 M 行,每行描述一个操作,格式如题目中所述。
输出格式
输出文件包含一个整数,表示所有 Q 操作的结果的和。
3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2
5
提示
初始序列为 {1,2,4}。
Q 1:仅 a2=2 满足 (ak&2i)>0,该操作的结果为 1。
Q 2:仅 a3=4 满足 (ak&2i)>0,该操作的结果为 1。
A 1:原序列变为 {2,3,5}。
Q 1:仅 a1=2,a2=3 满足 (ak&2i)>0,该操作的结果为 2。
Q 2:仅 a3=5 满足 (ak&2i)>0,该操作的结果为 1。
1+1+2+1=5,所以最终结果为 5。
30% 的数据满足 1≤N≤100,1≤M≤1000。
100% 的数据满足1≤N,M≤105。