[BJWC2008] 序列
题目描述
对一个长度为$N$的序列$\{a_n\}(a_i\in[0,2^{16}-1])$,进行如下两种,共计$M$个操作:
1. `A x`$(x\ge0)$:$a_i=a_i+x\mod2^{16}$
2. `Q i`:询问$Card\{k\mid(a_k\;\&\;2^i)>0,1\le k\le N,k\in\mathbb{Z}\}$的结果
其中$\&$运算符为相当于C/C++中的`&`或Pascal中的`and`
给定初始序列和操作序列,请你模拟操作过程,并计算所有$Q$操作的相应的结果的和。
输入输出格式
输入格式
输入文件的第一行包含两个以空格分隔的整数,分别代表$N,M$
接下来的$N$行每行包含一个整数,代表初始序列
接下来的$M$行,每行描述一个操作,格式如题目中所述
输出格式
输出文件包含一个整数,表示所有$Q$操作的结果的和
输入输出样例
输入样例 #1
3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2
输出样例 #1
5
说明
初始序列为$1\;2\;4$
`Q 1`:仅$a_2=2$满足$(a_k\;\&\;2^i)>0$,该$Q$操作的结果为$1$
`Q 2`:仅$a_3=4$满足$(a_k\;\&\;2^i)>0$,该$Q$操作的结果为$1$
`A 1`:原序列变为$2\;3\;5$
`Q 1`:仅$a_1=2,a_2=3$满足$(a_k\;\&\;2^i)>0$,该$Q$操作的结果为$2$
`Q 2`:仅$a_3=5$满足$(a_k\;\&\;2^i)>0$,该$Q$操作的结果为$1$
$1+1+2+1=5$,所以最终结果为5
$30\%$的数据满足$1\le N\le100,1\le M\le1000$
$100\%$的数据满足$1\le N,M\le10^5$