题解：P12555 [UOI 2024] AND Array

· · 题解

Solution

高一的时候我们教练往 CSP 模拟赛里扔了一个这样的题：

给定一个长度为 10^5 的，值域在 [0,2^{18}) 中的数组 a。每次给定 (x,v)，求出最小的 i \ge x，使得 a_i \text{ and } v=0。

当时就整出了一个这样的做法：从后往前扫描 x。查询的时候将 v 取反，即要求 a_i \subseteq v。

然后有两种做法：插入 a_i 的时候，暴力扫描其所有超集；或者询问 v 的时候，查询其所有子集。

发现这样询问和修改必须有一个是 O(1) 有一个是 O(V)。考虑根号分治，对于后 9 位做一种算法，对于前 9 位做另一种算法。即在 O(n \sqrt V) 的复杂度内解决了这个题。

回到这道题，我们现将 a_i=0 的位置剔除。直接做 O(nb) 次询问。

每次询问，我们先找到一个 a_i 使得 a_i \text{ and } x =0。然后 x \leftarrow x \text{ or } a_i。不断重复此过程。

显然我们找到的 i 一定是递增的，符合题目要求。而在 b 次操作后此过程一定会终止。

所以说，我们这时候有 n 次修改，nb^2 次查询。那么很容易平衡到 O(nb \sqrt{2^b})。

最短解，跑得也挺快。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXM=(1<<20)+10;
int n,b,a[MAXN],vis[MAXM],l;
ll sum,ans[MAXN];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>b,l=min(b,14);
    ffor(i,1,n) cin>>a[i];
    roff(i,n,1) {
        if(!a[i]) sum+=i;
        else {
            int dt=(1<<l)-1-(a[i]&((1<<l)-1)),ot=(((a[i]>>l)+1)<<l)-1;
            for(int s=dt;s;s=(s-1)&dt) vis[ot-s]=i;
            vis[ot]=i;
        }
        ans[i]=b*sum;
        ffor(j,0,b-1) {
            int ot=(1<<b)-1-(1<<j);
            while(1) {
                int x=(ot>>l)<<l,y=ot-x,nxt=n+1;
                for(int s=x;s;s=(s-1)&x) if(vis[s+y]) nxt=min(nxt,vis[s+y]);
                if(vis[y]) nxt=min(nxt,vis[y]);
                if(nxt==n+1) break ;
                ans[i]+=nxt,ot-=a[nxt];
            }
        }
    }
    ffor(i,1,n) cout<<ans[i]<<' ';
    return 0;
}