题解：P17110 「FAOI-R13」XOR and Less（贪心）

· · 题解

思路

考虑一个已经确定答案的区间，若在区间末尾新增一个数，如何快速更新答案。设新增的数的上限为 a，当前区间答案为 s。我们从高位到低位逐位比较 a 与 s 的二进制位。若 a 的当前位为 1，则有两种情况：

  1. 若 s 的这一位为 0，贪心地将 s 的这一位也设为 1；
  2. 若 s 的这一位已经为 1，则 a 的这一位无法继续提升 s，但注意到新增数的取值范围是 [0,a]，此时我们可以选择让新增数在该位取 0，并允许所有更低位的取值任意，于是可以直接将 s 在该位之后的所有低位全部置为 1。

因此，朴素做法可以枚举左端点 l，然后逐个向右扩展右端点 r，动态维护当前答案并累加，复杂度为 O(n^2\log V)，需要优化。

观察发现，s 的二进制位一旦变为 1，之后永远不会再变为 0。因此在整个扩展过程中，s 至多被更新 \log V 次。换句话说，对于每个固定的左端点，内层循环中真正引起 s 变化的位置只有 O(\log V) 个。

现在的问题是如何快速跳过那些不会改变 s 的位置。设 j 为 s 中最低的为 0 的二进制位（即从低位开始第一个 0 位），则一个新数 a 能够更新 s，当且仅当 a 的最高位（最高的为 1 的二进制位）大于或等于 j；否则 a 不会改变 s。

利用这个性质，我们可以预处理数组 nxt_{i,j}：表示从位置 i 开始（i 之后），当 s 的最低 0 位为 j 时，第一个能够更新 s 的位置；若不存在则设为 n+1。该数组可以通过从后向前递推在 O(n\log V) 时间内完成。

在内层循环时，只需额外维护当前 s 的最低 0 位，每次直接跳转到 nxt 所指向的位置，并在该位置进行更新。总时间复杂度为 O(n\log^2 V)。

完整代码

赛时代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5,mod=998244353;
void read(int&x){
    int t=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))t=(t<<3)+(t<<1)+c-48,c=getchar();
    x=t;
}
int n,a[N],sum,nxt[N][32];
ll ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=0;i<=31;i++)nxt[n][i]=n+1;
    for(int i=n-1;i>=1;i--){
        if(!a[i+1]){
            for(int j=0;j<=31;j++)nxt[i][j]=nxt[i+1][j];
            continue;
        }
        int t=__lg(a[i+1]);
        for(int j=0;j<=t;j++)nxt[i][j]=i+1;
        for(int j=t+1;j<=31;j++)nxt[i][j]=nxt[i+1][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=i,sum=0,cnt=0;j<=n;j=nxt[j][cnt]){
            int aa=a[j];
            while(aa){
                int t=(1<<__lg(aa));
                if((sum|t)==sum){sum|=t-1;break;}
                sum|=t,aa^=t;
            }
            for(;sum&(1<<cnt);cnt++);
            ans=(ans+(ll)sum*(nxt[j][cnt]-j))%mod;
        }
    }
    cout<<ans;
    return 0;
}

本文在写作完成后使用 DeepSeek 进行了润色。