33OJ
登录 注册

#P4641. [BJWC2008] 序列

[BJWC2008] 序列

题目描述

对一个长度为 NN 的序列 {an}(ai∈[0,216−1])\{a_n\}(a_i\in[0,2^{16}-1]),进行如下两种,共计 MM 个操作:

  1. A x(x≥0)(x\ge0):执行 ai←(ai+x) mod 216a_i\leftarrow(a_i+x)\bmod2^{16}。

  2. Q i:询问 $\#\{k\mid(a_k\;\&\;2^i)>0,1\le k\le N,k\in\mathbb{Z}\}$ 的结果,其中 #A\#A 表示集合 AA 的大小。

其中 &\& 运算符为相当于 C/C++ 中的 & 或 Pascal 中的 and。

给定初始序列和操作序列,请你模拟操作过程,并计算所有 QQ 操作的相应的结果的和。

输入格式

输入文件的第一行包含两个以空格分隔的整数,分别代表 N,MN,M。

接下来的 NN 行每行包含一个整数,代表初始序列。

接下来的 MM 行,每行描述一个操作,格式如题目中所述。

输出格式

输出文件包含一个整数,表示所有 QQ 操作的结果的和。

3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2
5

提示

初始序列为 {1,2,4}\{1,2,4\}。

Q 1:仅 a2=2a_2=2 满足 (ak  &  2i)>0(a_k\;\&\;2^i)>0,该操作的结果为 11。

Q 2:仅 a3=4a_3=4 满足 (ak  &  2i)>0(a_k\;\&\;2^i)>0,该操作的结果为 11。

A 1:原序列变为 {2,3,5}\{2,3,5\}。

Q 1:仅 a1=2,a2=3a_1=2,a_2=3 满足 (ak  &  2i)>0(a_k\;\&\;2^i)>0,该操作的结果为 22。

Q 2:仅 a3=5a_3=5 满足 (ak  &  2i)>0(a_k\;\&\;2^i)>0,该操作的结果为 11。

1+1+2+1=51+1+2+1=5,所以最终结果为 55。

30%30\% 的数据满足 1≤N≤100,1≤M≤10001\le N\le100,1\le M\le1000。

100%100\% 的数据满足1≤N,M≤1051\le N,M\le10^5。