sum nowcode

时间限制：1秒空间限制：131072K

题目描述

考虑维护一个这样的问题：
（1）给出一个数组A，标号为1~n
（2）修改数组中的一个位置。
（3）询问区间[l,r]中所有子集的位运算and之和mod(109+7)。
位运算and即为“pascal中的and”和“C/C++中的&”
我们定义集合S={ l , l+1 , ... , r-1 , r}
若集合T，T ∩ S = T，则称T为S的子集
设f（T）=AT1 and AT2 and ... and ATk (设k为T集大小，若k=0则f(T)=0)
所有子集的位运算and之和即为∑f(T)
那么，现在问题来了。

输入描述:

第一行，一个正整数N
第二行，N个非负整数，为数组A
第三行，一个正整数M，为操作次数
接下来M行格式如下
修改操作： 1 x y，将Ax修改为y
询问操作： 2 l r，区间[l,r]中所有子集的位运算and之和 mod(109+7)

输出描述:

对于每次询问输出一行，为该次询问的答案mod(109+7)。
long long 请使用lld

示例1

输入

输出

对于二进制下每一位，我们单独算其在区间内的贡献，最后加起来就是查询答案。
我们对二进制下每一位（最多31位）都建一个树状数组bit[i]，保存二进制下第i位为1的数字个数的前缀和。然后修改和增加这个无需赘言，修改要先把修改位置对应二进制下的1从bit中删掉再增加新的数字的bit。查询则是：若对应区间[i，j]在二进制下第k位有p个数字，那么贡献为(2^p-1)*2^k。每一位的贡献加起来就是答案。

 1 #include<bits/stdc++.h>
 2 #define clr(x) memset(x,0,sizeof(x))
 3 #define clr_1(x) memset(x,-1,sizeof(x))
 4 #define LL long long
 5 #define mod 1000000007
 6 using namespace std;
 7 const int N=1e5+10;
 8 const int M=1e9+10;
 9 int num[N];
10 int bit[35][N];
11 int n,m,k,u,v,op,t;
12 LL ans;
13 LL quick_pow(LL x,int n)
14 {
15     LL res=1;
16     while(n)
17     {
18         if(n&1) res=(res*x)%mod;
19         x=(x*x)%mod;
20         n>>=1;
21     }
22     return res;
23 }
24 void add(int i,int x,int pos)
25 {
26     while(i<=n)
27     {
28         bit[pos][i]+=x;
29         i+=i&-i;
30     }
31     return ;
32 }
33 int sum(int i,int pos)
34 {
35     int s=0;
36     while(i>0)
37     {
38         s+=bit[pos][i];
39         i-=i&-i;
40     }
41     return s;
42 }
43 int main()
44 {
45     scanf("%d",&n);
46     clr(bit);
47     for(int i=1;i<=n;i++)
48     {
49         scanf("%d",&num[i]);
50         k=0;
51         t=num[i];
52         while(t)
53         {
54             if(t&1) add(i,1,k);
55             t>>=1;
56             k++;
57         }
58     }
59     scanf("%d",&m);
60     for(int i=1;i<=m;i++)
61     {
62         scanf("%d%d%d",&op,&u,&v);
63         if(op==1)
64         {
65             k=0;
66             t=num[u];
67             while(t)
68             {
69                 if(t&1) add(u,-1,k);
70                 t>>=1;
71                 k++;
72             }
73             num[u]=t=v;
74             k=0;
75             while(t)
76             {
77                 if(t&1) add(u,1,k);
78                 t>>=1;
79                 k++;
80             }
81         }
82         if(op==2)
83         {
84             ans=0;
85             for(k=0;k<=32;k++)
86             {
87                 ans=(ans+(quick_pow(2,sum(v,k)-sum(u-1,k))-1)*quick_pow(2,k)%mod)%mod;
88             }
89             printf("%lld
",ans);
90         }
91     }
92     return 0;
93 }

View Code