思路

题目要求区间 $[l,r]$ 的的所有子集的与的和。让我们来想想与有什么特殊的性质。
数据给出 $A_{i}$ 不超过 $10^9$ ，同时作为位运算的与，我们可以看看每个数的二进制的每一位有什么用。
我们知道，不同数互与操作时，二进制下每一位是互不干扰的，这就给我们一个思路了。我们可以把所有区间拆成 $32$ 个区间，分别代表二进制下不同位的区间。那这和问题要问的有什么关系呢？
其实很容易发现，拆开区间后，我们一个区间子集的所有与操作和加起来其实就是这32个区间的与的和加起来。现在这 $32$ 个区间分别代表的就是每一位的区间，这样计算大大简化。那么题目要求的就是 $\sum_{k=1}^{31}2^k*2^{(\sum_{i=l}^{r}[(a[i]\&(1<<k))>0])-1}$ 。
解释一下这式子什么意思，首先累加 $32$ 个位的区间的答案（刚才说过的），接着考虑对于第 $k+1$ 位时，如果区间有 $m$ 个数是满足这意味是 $1$ 的话，那么这一位子集的答案不为 $0$ 的就是这 $m$ 个数的随机组合，随机组合其实有 $\sum_{i=1}^{m}C_{m}^{i}$ ，注意取0个时不是答案，其实也就是 $\sum_{i=0}^{m}C_{m}^{i}-1$ ，而 $\sum_{i=0}^{m}C_{m}^{i}=2^m$ ，所以只要求出该位下区间有多少个数满足情况就可以算了。
可以用线段树维护 $\sum_{i=l}^{r}[(a[i]\&(1<<k))>0]$ ，但是我线段树写炸了，用了常数更小的树状数组维护QAQ。建议预处理出 $1$ 到 $n$ 的 $2$ 的次方数，然后 $O(1)$ 调用。

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=1e9+7;

ll a[maxn],n,m,mx,maxv,op,c,d;
ll lg[maxn],t[32][maxn];
//struct node{
//    int l,r,w;
//}t[32][maxn<<2];

char buf[1<<20],*P1=buf,*P2=buf;    
//#define gc() getchar()
#define gc() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<20,stdin),P1==P2)?EOF:*P1++)
#define TT template<class T>inline
TT void read(T&x)
{
       x=0; char c=gc(); bool f=0;
       while(c<48||c>57){f^=c=='-',c=gc();}
       while(47<c&&c<58)x=(x<<3)+(x<<1)+(c^48),c=gc();
       if(f)x=-x;
}

//ll qpow(ll a,ll b)
//{
//    ll ans=1;
//    while(b)
//    {
//        if(b&1)ans=ans*a%mod;
//        b>>=1; a=a*a%mod;
//    }
//    return ans;
//}
//
//inline void pushup(int k,int p)
//{
//    t[p][k].w=t[p][k<<1].w+t[p][k<<1|1].w;
//}
//
//inline void build(int k,int l,int r)
//{
//    for(int i=0;i<=mx;i++)t[i][k].l=l,t[i][k].r=r;
//    if(l==r)
//    {
//        for(int i=0;i<=mx;i++)t[i][k].w=(a[l]&(1<<i))>0;
//        return;
//    }
//    int mid=l+r>>1;
//    build(k<<1,l,mid);
//    build(k<<1|1,mid+1,r);
//    for(int i=0;i<=mx;i++)pushup(k,i);
//    return;
//}
//
//inline void update(int k,int p,int u,int v)
//{
//    int l=t[p][k].l,r=t[p][k].r;
//    if(l==r)
//    {
//        t[p][k].w=v; return;
//    }
//    int mid=l+r>>1;
//    if(u<=mid)update(k<<1,p,u,v);
//    else update(k<<1|1,p,u,v);
//    pushup(k,p);
//    return;
//}
//
//inline int query(int k,int p,int l,int r)
//{
//    int x=t[p][k].l,y=t[p][k].r;
//    if(l<=x&&y<=r)return t[p][k].w;
//    int mid=x+y>>1;
//    int res=0;
//    if(l<=mid)res+=query(k<<1,p,l,r);
//    if(mid<r)res+=query(k<<1|1,p,l,r);
//    return res;
//}

inline int lowbit(int x)
{
    return x&(-x);
}

inline void update(int x,int p,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))t[p][i]+=y;
}

inline int query(int x,int p)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))res+=t[p][i];
    return res;
}

int main()
{
    read(n); mx=31; lg[0]=1;
    for(int i=1;i<=n;i++)
    {
        read(a[i]); int k=a[i],cnt=0;
        while(k)
        {
            if(k&1)update(i,cnt,1);
            k>>=1; cnt++;
        }
    }
    for(int i=1;i<=n;i++)lg[i]=lg[i-1]*2%mod;
//    build(1,1,n);
    read(m);
    while(m--)
    {
        read(op),read(c),read(d);
        ll ans=0;
        if(op==1)
        {
            for(int i=0;i<=mx;i++)
            {
                if((a[c]&(1<<i))!=(d&(1<<i)))
                {
//                    update(1,i,c,(d&(1<<i))>0);
                    update(c,i,(d&(1<<i))>0?1:-1);
                }
            }
            a[c]=d;
        }
        else
        {
            ll ans=0;
            for(int i=0;i<=mx;i++)
            {
//                ans+=lg[i]*(lg[query(1,i,c,d)]-1)%mod;
                ans=(ans+lg[i]*(lg[query(d,i)-query(c-1,i)]-1))%mod;
            }
            printf("%lld\n",ans);
        } 
    } 
    return 0;
}

题解 | #Sum#

思路