该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有一个长度为 N 的序列 a (ai∈[0,216−1])
你可以进行如下两种,共计 M 个操作:
-
A x (x≥0):ai=(ai+x)mod216
-
Q i:询问 $Card\{k\mid(a_k\;\&\;2^i)>0,1 ≤ k ≤ N,k\in\mathbb{Z}\}$ 的结果
其中 & 表示按位与运算
给定初始序列和操作序列,请你模拟操作过程,并计算所有 Q 操作的相应结果的和。
输入格式
第一行包含两个以空格分隔的整数,分别代表 N,M
接下来的 N 行每行包含一个整数,代表初始序列
接下来的 M 行,每行描述一个操作,格式如题目中所述
输出格式
包含一个整数,表示所有 Q 操作的结果的和
输入输出样例
输入
3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2
输出
5
解释
初始序列为 124
Q 1:仅 a2=2 满足 (ak&2i)>0,该 Q 操作的结果为 1
Q 2:仅 a3=4 满足 (ak&2i)>0,该 Q 操作的结果为 1
A 1:原序列变为 235
Q 1:仅 a1=2,a2=3 满足 (ak&2i)>0,该 Q 操作的结果为 2
Q 2:仅 a3=5 满足(ak&2i)>0,该 Q 操作的结果为 1
1+1+2+1=5,所以最终答案为 5 。
数据范围
30% 的数据满足 1≤N≤100,1≤M≤1000
100% 的数据满足 1≤N,M≤105