时间限制：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 2 362 1 31 1 22 1 32 2 31 2 52 1 3

输出

915713

---

对于二进制下每一位，我们单独算其在区间内的贡献，最后加起来就是查询答案。

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

1 #include
           
             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\n",ans);90         }91     }92     return 0;93 }