E题

看了官方讲解视频的思路后才写出来

1.设f[l,r]==(a l ​ & a l+1 ​ &...& a r ​ )⊕(a l ​ ∣ a l+1 ​ ∣...∣ a r ​)

2.根据f[l,r]表达式，仅观察[l,r]中二进制数第k位的情况下，同时出现1和0才能使f[l,r]的第k位是1

3.那么符合题意的区间f[l,r]的二进制数最高位1的位数必须在[k1,k2-1]中

4.用双指针或者二分预处理出数组l[k][i]:在第k位下，从第i个数到第l[k][i]个数第一次同时出现0和1，即第一次出现f[l,r]在第k位下等于1

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k1,k2,a[500005],l[65][500005];

signed main()
{
    cin>>n>>k1>>k2;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    if(k1>=60)
    {
        cout<<0;
        return 0;
    }
    
    int len=60;//1e18的二进制数长为60
    for(int k=0;k<len;k++)//枚举位数，然后用双指针算法处理出数组l[][]
    {
        int cnt0=0,cnt1=0;//0的个数，1的个数
        for(int i=1,j=1;j<=n;j++)
        {
            int t=((a[j]>>k)&1);
            t?cnt1++:cnt0++;
            while(cnt0 && cnt1)//同时存在0和1
            {
                l[k][i]=j;
                int t=((a[i++]>>k)&1);
                t?cnt1--:cnt0--;
            }
        }
    }
    
    //符合条件的区间：f[l,r]的二进制数最高1的位数在[k1,k2-1]
    int ans=0;
    for(int i=1;i<=n;i++)//枚举左边界
    {
        int a=n+1,b=n+1;
        for(int k=k1;k<len;k++)
        {
            if(l[k][i]==0)continue;
            if(k<=k2-1)a=min(a,l[k][i]);
            else b=min(b,l[k][i]);
        }
        if(a==n+1)continue;
        ans+=max(b-a,0LL);
    }
    cout<<ans;
    
    return 0;
}