位查询【 openjudge数据结构课程练习题】

/*=======================================================
位查询
http://dsalgo.openjudge.cn/linearlists/3/

总时间限制:5000ms 内存限制: 65536kB
描述
        给出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的统计值，每一个查询操作统计结果输出为一行。
样例输入
    3 5
    1 2 4
    Q 1
    Q 2
    C 1
    Q 1
    Q 2
样例输出
    1
    1
    2
    1
提示
    只输出查询操作Q的统计值。
=========================================================*/

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<stdlib.h>
 4 int main()
 5 {
 6     long N,M;
 7     long *a;
 8     char ch;
 9     long j,d;
10     long i;
11     long ans;
12     freopen("data.in","r",stdin);
13     freopen("data.out","w",stdout);
14     scanf("%ld%ld",&N,&M);
15     
16     a=(long *)malloc(N*sizeof(long));
17     for(j=0;j<N;j++) scanf("%ld",&a[j]);
18     getchar();//注意这里。
19     for(j=0;j<M;j++)
20     {
21         scanf("%c %ld",&ch,&d);
22         getchar();//注意这里。
23         /*printf("%c %ld\n",ch,d);*/
24         
25         if(ch=='C')
26         {
27             for(i=0;i<N;i++)
28                 a[i]=(a[i]+d)%65535;
29         }
30         else if(ch=='Q')
31         {
32             ans=0;
33             d=pow(2,d);
34             for(i=0;i<N;i++)
35                 if(a[i]&d) ans++;
36             printf("%ld\n",ans);
37         }
38         else printf("input error!ch==%c\n",ch);
39     }
40     return 0;
41 }