鏈接：https://ac.nowcoder.com/acm/problem/14269
來源：牛客網(wǎng)

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 131072K，其他語言262144K
64bit IO Format: %lld
題目描述
考慮維護一個這樣的問題：
（1） 給出一個數(shù)組A，標號為1~n
（2） 修改數(shù)組中的一個位置。
（3） 詢問區(qū)間[l,r]中所有子集的位運算and之和mod(109+7)。
位運算and即為“pascal中的and”和“C/C++中的&”
我們定義集合S={ l , l+1 , … , r-1 , r}
若集合T，T ∩ S = T，則稱T為S的子集
設(shè)f（T）=AT1 and AT2 and … and ATk (設(shè)k為T集大小，若k=0則f(T)=0)
所有子集的位運算and之和即為∑f(T)
那么，現(xiàn)在問題來了。
輸入描述:
第一行，一個正整數(shù)N
第二行，N個非負整數(shù)，為數(shù)組A
第三行，一個正整數(shù)M，為操作次數(shù)
接下來M行格式如下
修改操作： 1 x y，將Ax修改為y
詢問操作： 2 l r，區(qū)間[l,r]中所有子集的位運算and之和 mod(109+7)
輸出描述:
對于每次詢問輸出一行，為該次詢問的答案mod(109+7)。
long long 請使用lld
示例1
輸入
復制
3
1 2 3
6
2 1 3
1 1 2
2 1 3
2 2 3
1 2 5
2 1 3
輸出
復制
9
15
7
13
說明
第一次詢問：
Answer =1+2+3+(1 and 2)+(1 and 3)+(2 and 3)+(1 and 2 and 3)
=1+2+3+0+1+2+0
=9
第二次詢問：
Answer =2+2+3+(2 and 2)+(2 and 3)+(2 and 3)+(2 and 2 and 3)
=2+2+3+2+2+2+2
=15
第三次詢問：
Answer =2+3+(2 and 3)
=2+3+2
=7
第四次詢問：
Answer =2+5+3+(2 and 5)+(2 and 3)+(3 and 5)+(2 and 5 and 3)
=2+5+3+0+2+1+0
=13
備注:
M,N≤10⁵,Ai≤10⁹

題解：

這種位運算多半都與二進制有關(guān)系
我們把每個數(shù)進行拆分，然后統(tǒng)計每一位上每個數(shù)貢獻了多少1
很多題解都提到式子：
(2^x-1) * 2^p
x是這一位為1的數(shù)的個數(shù)
p：是指第p位
怎么來的呢？
2^x-1
其實就是比如說有x個數(shù)字某一位都有1
答案=x+ （x中任取兩個取對）+(x中任取三個)+（x中任取x-1個）=2^x-1
（高中數(shù)學都學過）
線段樹和樹狀數(shù)組都可以做

代碼：

該為本人寫的代碼。。為錯誤代碼，但我沒找到原因

#include<bits/stdc++.h> using namespace std; const int maxn=2e5+9; typedef long long ll; ll mod=1e9+7; struct node{int a[40]; }p[maxn<<2]; ll b[maxn]; void init() {b[0]=1;for(int i=1;i<=32;i++)b[i]=b[0]<<i%mod; } void build(int l,int r,int rt) {if(l==r){ll x;cin>>x;for(int i=0;i<=32;i++){p[rt].a[i]=x%2;x/=2;}return ;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1+1);for(int i=0;i<=32;i++){p[rt].a[i]=p[rt<<1].a[i]+p[rt<<1+1].a[i];//左右子樹的第i位相加 }return ; } void update(int pos,int v,int l,int r,int rt)//將第pos位置的數(shù)改成v {if(l==r){for(int i=0;i<=32;i++){p[rt].a[i]=v%2;v/=2;}return ;}int mid=(l+r)>>1;if(pos<=mid) update(pos,v,l,mid,rt*2);else update(pos,v,mid+1,r,rt*2+1);for(int i=0;i<32;i++){p[rt].a[i]=p[rt*2].a[i]+p[rt*2+1].a[i];}return ; } node query(int L,int R,int l,int r,int rt) {if(L>=l&&R<=r) return p[rt];int mid=(l+r)>>1;node p1,p2,p3; // memset(p1.a,0,sizeof(p1.a)); // memset(p2.a,0,sizeof(p2.a));if(L<=mid)p1=query(L,R,l,mid,rt<<1);if(R>mid)p2=query(L,R,mid+1,r,rt<<1+1);for(int i=0;i<=32;i++)p3.a[i]=p1.a[i]+p2.a[i];return p3;} int main() {ios::sync_with_stdio(false);init();int n;cin>>n;build(1,n,1);//root int q;cin>>q;while(q--){int x,l,r;cin>>x>>l>>r;if(x==1)update(l,r,1,n,1);else {node res=query(l,r,1,n,1);ll sum=0;for(int i=0;i<=32;i++){sum=(sum+b[i]*(b[res.a[i]-1])%mod)%mod;}cout<<sum<<endl;}}return 0; }

樹狀數(shù)組做法：

#include<stdio.h> #include<algorithm> using namespace std; #define maxn 100005 #define mod 1000000007 #define lowbit(x) x&(-x) typedef long long ll; int n,m,a[maxn],p[maxn],c[35][maxn]; void add(int k,int x,int val) {while(x<=n){c[k][x]+=val;x+=lowbit(x);} } int sum(int k,int x) {int res=0;while(x){res+=c[k][x];x-=lowbit(x);}return res; } int main(void) {p[0]=1;int i,j,t,x,y;scanf("%d",&n);for(i=1;i<=n;i++)p[i]=1ll*2*p[i-1]%mod;for(i=1;i<=n;i++){scanf("%d",&a[i]);for(j=0;j<=30;j++)if(a[i]&(1<<j))//如果第j位是1的話 add(j,i,1);//在該位上添加1 }scanf("%d",&m);while(m--){scanf("%d%d%d",&t,&x,&y);if(t==1){for(i=0;i<=30;i++)if(a[x]&(1<<i))add(i,x,-1);a[x]=y;for(i=0;i<=30;i++)if(a[x]&(1<<i))add(i,x,1);}else{ll ans=0;for(i=0;i<=30;i++){int tmp=sum(i,y)-sum(i,x-1);//查詢x到y(tǒng)區(qū)間內(nèi)在第i位上1的個數(shù) ans=(ans+1ll*(p[tmp]-1)*p[i]%mod)%mod;}printf("%d\n",ans);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。