bzoj#P1273. [BeiJingWc2008] 序列
[BeiJingWc2008] 序列
题目描述
对一个长度为 的整数序列 ,进行如下两种,共计 个操作:
A x
::。Q i
:询问 $Card\{k|(a_k\& 2^i)>0,~1 \leq k \leq N,~k \in \mathcal Z\}$ 的结果。
其中 & 运算符为相当于 C/C++ 中的 & 或者 Pascal 中的 and。
给定初始序列和操作序列,请你模拟操作过程,并计算所有 Q 操作的相应的结果的和。
输入格式
输入文件的第一行包含两个以空格分隔的整数,分别代表 , 。
接下来的 行,每行包含一个整数,代表初始序列。
接下来的 行,每行描述一个操作,格式如题目中所述。
输出格式
输出文件包含一个整数,表示所有 操作的结果的和。
3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2
5
样例解释
初始序列为:1 2 4。
Q 1:仅 满足 ,该 Q 操作的结果为 。
Q 2:仅 满足 ,该 Q 操作的结果为 。
A 1:原序列变为 2 3 5。
Q 1:仅 满足 ,该 Q 操作的结果为 。
Q 2:仅 满足 ,该 Q 操作的结果为 。
,所以最终结果为 。
数据范围
对于 的数据满足 ;
对于 的数据满足 。