ICPC 2017 西安 G（线段树）

[题目链接](https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-A1613) ------------ 考虑二进制下每一位的贡献 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls i<<1 #define rs i<<1|1 #define mid (l+r)/2 const int M=1e5+10,mod=1e9+7; int n,q,a[M]; struct d { ll len,num[20],cnt[20],lc[20],rc[20]; }tree[M*4]; d up(d a,d b) { d res; res.len=a.len+b.len; for(int j=0;j<=19;j++) { res.num[j]=a.num[j]+b.num[j]; res.cnt[j]=a.cnt[j]+b.cnt[j]+a.rc[j]*(b.len-b.lc[j])+(a.len-a.rc[j])*b.lc[j]; if(a.num[j]&1)res.lc[j]=a.lc[j]+b.len-b.lc[j]; else res.lc[j]=a.lc[j]+b.lc[j]; if(b.num[j]&1)res.rc[j]=b.rc[j]+a.len-a.rc[j]; else res.rc[j]=b.rc[j]+a.rc[j]; } return res; } void build(int i,int l,int r) { if(l==r) { tree[i].len=1; for(int j=0;j<=19;j++) tree[i].num[j]=tree[i].lc[j]=tree[i].rc[j]=tree[i].cnt[j]=((a[l]>>j)&1); return ; } build(ls,l,mid); build(rs,mid+1,r); tree[i]=up(tree[ls],tree[rs]); } d que(int i,int l,int r,int ql,int qr) { if(l==ql&&r==qr)return tree[i]; if(qr<=mid)return que(ls,l,mid,ql,qr); else if(ql>mid)return que(rs,mid+1,r,ql,qr); else { d t1=que(ls,l,mid,ql,mid); d t2=que(rs,mid+1,r,mid+1,qr); return up(t1,t2); } } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,1,n); while(q--) { int l,r;scanf("%d%d",&l,&r); d res=que(1,1,n,l,r); ll ans=0; for(int i=0,p=1;i<=19;i++,p=p*2%mod) ans=(ans+res.cnt[i]%mod*p%mod)%mod; printf("%lld\n",ans); } } return 0; } ```