#937. 序列问题

序列问题

题目描述

有一个长度为 NN 的序列 aa (ai∈[0,216−1])(a_i\in[0,2^{16}-1])

你可以进行如下两种,共计 MM 个操作:

  1. A x (x≥0)(x\ge0):ai=(ai+x)mod  216a_i=(a_i+x)\mod2^{16}

  2. Q i:询问 $Card\{k\mid(a_k\;\&\;2^i)>0,1 ≤ k ≤ N,k\in\mathbb{Z}\}$ 的结果

其中 &\& 表示按位与运算

给定初始序列和操作序列,请你模拟操作过程,并计算所有 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  41\;2\;4

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

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

A 1:原序列变为 2  3  52\;3\;5

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

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

1+1+2+1=51+1+2+1=5,所以最终答案为 55 。

数据范围

30%30\% 的数据满足 1≤N≤100,1≤M≤10001 ≤ N ≤100,1 ≤ M ≤1000

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