bzoj#P1273. [BeiJingWc2008] 序列

[BeiJingWc2008] 序列

题目描述

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

  1. A x(x0)(x \geq 0)ai=(ai+x)mod216a_i=(a_i+x) \bmod 2^{16}
  2. Q i:询问 $Card\{k|(a_k\& 2^i)>0,~1 \leq k \leq N,~k \in \mathcal Z\}$ 的结果。

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

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

输入格式

输入文件的第一行包含两个以空格分隔的整数,分别代表 NN, MM

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

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

输出格式

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

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

样例解释

初始序列为:1 2 4。

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

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

A 1:原序列变为 2 3 5。

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

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

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

数据范围

对于 30%30\% 的数据满足 1N100, 1M10001 \leq N \leq 100,~1 \leq M \leq 1000

对于 100%100\% 的数据满足 1N,M1051 \leq N,M \leq 10^5