05345: 位查询

http://cs101.openjudge.cn/practice/05345/

给出N个范围在[0, 65535]的整数，编程支持以下的操作：

（1）修改操作：C d，所有的数都增加d。如果超过65535，把结果模65536。 0 <= d <= 65535 （2）查询操作：Q i，统计在N个正整数中有多少个整数其对应的二进制形式的第i位二进制位为非0。0 <= i <= 15。并且最低位i为0。

最后，输出所有查询操作的统计值。

输入

输入的第一行为两个正整数N,M,其中N为操作的整数的个数，而M为具体有多少个操作。输入的第二行为N个正整数，为进行操作的N个正整数。下面有M行，分别表示M个操作。

N<=100000,M<=200000

输出

输出所有查询操作Q的统计值，每一个查询操作统计结果输出为一行。

样例输入

样例输出

提示

只输出查询操作Q的统计值。

"最低位i为0"的意思是指编号上个位数是第零位。比如说 $4 = (100)_{2}$ ，这里面1是第二位，而不是第三位的意思。

python

n,m  = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
    op, i = input().split()
    i = int(i)
    if op == 'C':
        for j in range(n):
            a[j] += i
            a[j] %= 65535
    elif op == 'Q':
        cnt = 0
        for j in a:
            s = bin(j)[2:][::-1]
            if i < len(s) and s[i] == '1':
                cnt += 1
        print(cnt)

python

def modify_nums(nums, d):
    for i in range(len(nums)):
        nums[i] = (nums[i] + d) % 65536

def count_bits(nums, i):
    count = 0
    for num in nums:
        if (num >> i) & 1:
            count += 1
    return count

N, M = map(int, input().split())
nums = list(map(int, input().split()))

for _ in range(M):
    operation, value = input().split()
    if operation == 'Q':
        i = int(value)
        result = count_bits(nums, i)
        print(result)
    elif operation == 'C':
        d = int(value)
        modify_nums(nums, d)

05345: 位查询 ​

05345: 位查询