题解：P12555 [UOI 2024] AND Array

· · 题解

一个简单又好写的做法。

先不考虑所有的 0。

发现一个重要性质：我们如果在 i 找到产生贡献的下一个数 j，那么我们可以发现：如果在 j 后面还存在下一个数 k，我们可以在 j 去找它，也可以是在 i 找（第一个满足 a_k 与上 x 等于 0 的 k）。

考虑定期重构，我们每隔 B 个数就重新做一次高维前缀和，每次询问就是先走 B 步，然后再跳 b 次。

时间复杂度为 O(2^b b\frac{n}{B}+nb(b+B))。B=1000 左右最优。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int Maxn=1e5+5,B=1000;
int n,b;
int a[Maxn];
ll sum,ans[Maxn];
int last[1<<20],f[1<<20];
int main(){
    n=read();b=read();
    for(int i=1;i<=n;i++)a[i]=read();
    memset(last,0x7f,sizeof last);
    memset(f,0x7f,sizeof f);
    int id=n+1;
    for(int i=n;i;i--){
        if(!a[i])sum+=i,a[i]=(1<<b)-1;
        else{
            last[a[i]]=i;
        }ans[i]=sum*b;
        if(i%B==0){
            for(int i=0;i<(1<<b);i++)f[i]=last[i];
            for(int i=0;i<b;i++)
                for(int s=0;s<(1<<b);s++)if((s>>i)&1)f[s]=min(f[s],f[s^(1<<i)]);
            id=i;
        }
        for(int j=0;j<b;j++){
            int p=(1<<j);
            for(int k=i;k<id;k++){
                if(!(p&a[k]))p+=a[k],ans[i]+=k;
            }while(f[(1<<b)-1-p]<=n)ans[i]+=f[(1<<b)-1-p],p+=a[f[(1<<b)-1-p]];
        }
    }
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}