scp t2

· · 题解

首先我们拆贡献，拆成所有区间的按位或和之和，加上所有区间的 \operatorname{mex} 除去那些区间内已存在的位之后的和。

前面这一部分是好计算的，拆位然后正难则反，每一位假设总共 \frac{n(n+1)}{2} 个区间都有这个位，然后扫一遍找到所有极长的没有这个位的连续段，然后贡献是好计算的，这一部分时间复杂度 O(n\log V)。可以做到 O(n) 但是没必要。

我们看后面一部分什么时候会有贡献。暴力一下得出结论，只有当 \operatorname{mex} 为 2^k 的形式时才可能有贡献。证明：如果 \operatorname{mex}（设为 m）不是 2^k 的形式，那么根据 \operatorname{mex} 的定义，区间内一定有 0\sim m-1 的所有数，设小于 m 的最大的 2 的次幂是 2^k，那么区间内一定存在 2^k 和 2^k-1，这两个按位或就已经是 2^{k+1}-1 了，肯定包含 m 的所有位（因为最高位就是 2^k）。

我们枚举 \operatorname{mex}（记为 2^k），看一个区间什么时候有贡献。可以发现，一个区间有贡献的充要条件是：

我们枚举左端点，计算满足第一个条件的最左端的右端点，和不满足第二个条件的最左端的右端点，两者相减就是这个左端点对应的合法区间数（当然可能不存在合法区间，需要判一下）。这就是 AT_pakencamp_2023_day3_f，可以用双指针实现。枚举到每个 \operatorname{mex} 的时间复杂度是 O(n)，由于 \operatorname{mex} 不会超过 n，所以总共需要枚举 O(\log n) 个 \operatorname{mex}，所以这部分时间复杂度 O(n\log n)。

总时间复杂度 O(n\log V+n\log n)。

#include<bits/stdc++.h>
using namespace std;
unsigned long long ans=0;
int a[2000005];
int c[2000005];
int lp[2000005],rp[2000005];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ans=1073741823ull*(1ull*n*(n+1)/2);
    int cnt=0;
    for(int i=0;i<=29;i++){
        cnt=0;
        for(int j=1;j<=n;j++){
            if(a[j]&(1<<i))cnt=0;
            else cnt++;
            ans-=cnt*(1ull<<i);
        }
    }
    for(int i=0;i<=20;i++){
        int p=1;
        for(int j=0;j<(1<<i);j++)c[j]=0;
        int tot=0,cnt=0;
        for(int j=1;j<=n;j++){
            if(j>1&&a[j-1]<(1<<i)){
                c[a[j-1]]--;
                if(!c[a[j-1]])cnt--;
            }
            while(p<=n&&cnt<(1<<i)){
                if(a[p]<(1<<i)&&!c[a[p]])cnt++;
                if(a[p]<(1<<i))c[a[p]]++;
                p++;
            }
            if(cnt<(1<<i))lp[j]=n+1;
            else lp[j]=p-1;
        }
        int ci=0;
        p=1;
        for(int j=1;j<=n;j++){
            if(j>1&&(a[j-1]&(1<<i)))ci--;
            while(p<=n&&!ci){
                if(a[p]&(1<<i))ci++;
                p++;
            }
            if(ci)rp[j]=p-1;
            else rp[j]=n+1;
        }
        for(int j=1;j<=n;j++)ans+=max(rp[j]-lp[j],0)*(1ull<<i);
    }
    cout<<ans;
}
/*
祝世界上最可爱的灰之魔女伊蕾娜小姐生日快乐！
*/