每日一题 5.25 小AA的数列

这一题我是只想到暴力的 t了后面想到了以前写的一些题就算了二进制的前缀和
但还是t了 于是在学习了一番博客后 我学会了
我们先统计二进制前缀和 然后在统计前缀和的奇偶数的前缀和 因为要统计长度为偶数
所有是以二一跳的前缀和 有了这以后 我们枚举左端点 就可以O（1）求右端点以及贡献
对于范围lr 就从把1n改为lr

#include <bits/stdc++.h>
#define ll long long
const int N=1e5+5;
const int p=1e9+7;
using namespace std;
int n,l,r,a[N],b[N],f[N][31],dp[N][31][2];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>l>>r;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=29;j>=0;--j)
        {
            f[i][j]=f[i-1][j]+((a[i]>>j)&1);///二进制前缀和
            if(i!=1)
            {
                dp[i][j][0]=dp[i-2][j][0];///以二一跳的奇偶数前缀和
                dp[i][j][1]=dp[i-2][j][1];
            }
            ++dp[i][j][f[i][j]&1];///当前是奇是哦
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)///枚举左端点
    {
        int L=i+l-1,R=min(i+r-1,n);///最短与最长区间长度
        if((L-i+1)&1){///不能提前处理 l r
            ++L;
        }
        if((R-i+1)&1){
            --R;
        }
        if(L>R) continue;
        for(int j=29;j>=0;--j)
        {
            int k=((f[i-1][j]&1)^1);///相反位数  本来是奇 求偶数个数
            ll ins=dp[R][j][k];
            if(L!=1)
            {
                ins-=dp[L-2][j][k];
            }
            ans+=(ins*(1<<j))%p,ans%=p;///算贡献
        }
     //   cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}