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。每一位的贡献加起来就是答案。

 #include<bits/stdc++.h>

 #define clr(x) memset(x,0,sizeof(x))

 #define clr_1(x) memset(x,-1,sizeof(x))

 #define LL long long

 #define mod 1000000007

 using namespace std;

 const int N=1e5+;

 const int M=1e9+;

 int num[N];

 int bit[][N];

 int n,m,k,u,v,op,t;

 LL ans;

 LL quick_pow(LL x,int n)

 {

     LL res=;

     while(n)

     {

         if(n&) res=(res*x)%mod;

         x=(x*x)%mod;

         n>>=;

     }

     return res;

 }

 void add(int i,int x,int pos)

 {

     while(i<=n)

     {

         bit[pos][i]+=x;

         i+=i&-i;

     }

     return ;

 }

 int sum(int i,int pos)

 {

     int s=;

     while(i>)

     {

         s+=bit[pos][i];

         i-=i&-i;

     }

     return s;

 }

 int main()

 {

     scanf("%d",&n);

     clr(bit);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&num[i]);

         k=;

         t=num[i];

         while(t)

         {

             if(t&) add(i,,k);

             t>>=;

             k++;

         }

     }

     scanf("%d",&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&op,&u,&v);

         if(op==)

         {

             k=;

             t=num[u];

             while(t)

             {

                 if(t&) add(u,-,k);

                 t>>=;

                 k++;

             }

             num[u]=t=v;

             k=;

             while(t)

             {

                 if(t&) add(u,,k);

                 t>>=;

                 k++;

             }

         }

         if(op==)

         {

             ans=;

             for(k=;k<=;k++)

             {

                 ans=(ans+(quick_pow(,sum(v,k)-sum(u-,k))-)*quick_pow(,k)%mod)%mod;

             }

             printf("%lld\n",ans);

         }

     }

     return ;

 }

巴特西

sum nowcode

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章