XOR and Less

Shadow_T · 2026-06-18 21:49:00 · 题解

首先发现把 a_i 按二进制拆分成若干个 2^w 形式的元素以后，组成的新序列，其答案是不变的。即序列 a 可以等价为若干个 2^i 的形式的数组成的序列。

我们令 cnt_w 为当前 a_i 第 w 位为 1 的数的个数，即等价序列里 2^w 的数量。

对于每一位：

即答案只可能在加入一个数时出现 cnt_w 从 0 到 1，或者从 1 到 2 的时候被更新。枚举开头，每次找到最近的会可能让答案更新的点跳过去，中间的那一段答案不变，直接随便统计一下。由于每一位都会最多让你跳 2 次，对于同一个区间开头跳的次数是 O(\log v) 的，每次跳跃要用 O(\log v) 的复杂度找下一次跳跃的位置，枚举每一个开头，复杂度是 O(n \log^2v) 的。

精细实现可以做到 O(n \log v)。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fir first
#define sec second
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ll long long
#define int long long
#define umap unordered_map
const int maxn=5e5+10;
const int mod=998244353;
int a[maxn];
int ne[33][maxn];
int lg(int x)
{
    if(x==0) return 0;
    return __lg(x);
}
signed main()
{
    Ios();
    int n;
    cin>>n;
    REP(i,1,n) cin>>a[i];
    REP(w,0,32) ne[w][n+1]=1e9;
    REP(w,0,32)
    for(int i=n;i>=1;i--)
    if((a[i]>>w)&1) ne[w][i]=i;
    else ne[w][i]=ne[w][i+1];
    int ans=0;
    REP(i,1,n)
    {
        int sta=0,mx=0,neans=0;
        mx=max(mx,lg(sta&a[i]));
        sta|=a[i];
        neans=(sta|((1ll<<mx)-1));
        vector<int> ps;
        REP(w,0,32)
        {
            ps.pb(ne[w][i]);
            if(ne[w][i]<=n) ps.pb(ne[w][ne[w][i]+1]);
        }
        ps.pb(i),ps.pb(1e9);
        sort(all(ps));
        for(int j=0;j<ps.size()-1;j++)
        if(ps[j]!=ps[j+1])
        {
            int pos=ps[j];
            if(pos>=n) break;
            int mngx=min(ps[j+1],n);
            ans+=(mngx-pos)*neans;ans%=mod;
            mx=max(mx,lg(sta&a[mngx]));
            sta|=a[mngx];
            neans=(sta|((1ll<<mx)-1));
        }
        ans+=neans;ans%=mod;
    }
    cout<<ans;
}