题解：P12555 [UOI 2024] AND Array

a_foolish_OIer · 2026-11-10 18:34:00 · 题解

记 V=2^b，超级神秘做法，思维难度约等于 0。

把 a_i=0 去掉，注意到实际上只有 \log V 个位置有效，考虑把这些位置全部找出来，对于数 x 有效的位置 i 一定满足 x \mathbin{\&} a_i=0 \iff a_i \subseteq \overline{x}，可以使用高维前缀和在 O(n+V \log V) 维护出这一段是否存在 \subseteq x 的数，可以 O(1) 查询。

于是对序列分块，块长为 B，预处理 O(\frac{nV \log V}{B})，计算答案相当于处理 O(n\log V) 个询问，最多进入 O(\log V) 个块，扫一个块时间复杂度 O(B)，时间复杂度 O(\frac{nV \log V}{B}+n\log^2 VB)，平衡一下可以做到 O(n\sqrt V \log^{\frac{3}{2}} V)。

但是后半部分明显内存访问连续常数小，块长开到 1700 加一点剪枝就过了。

#include <bits/stdc++.h>
using namespace std;
mt19937 Rand(665431);
#define LL long long
#define i128 __int128
#define endl '\n'

const int N = 1e5 + 10;
const int M = 1e3 + 10;
const int inf = 1e9;
const int mod = 1e17 + 3;

int n,m,mxb,V,B;
int a[N],id[N],bl[N],br[N];
LL suf[N];
bitset <(1 << 20) + 10> vis[M];
map <int,int> res[M];

void solve(){
    cin >> n >> mxb; B = 1700; V = (1 << mxb) - 1;
    for (int i = 1 ; i <= n ; i++){
        cin >> a[i];
        id[i] = (i - 1) / B + 1;
        if (!bl[id[i]]) bl[id[i]] = i;
        br[id[i]] = i; m = id[i];
    }
    for (int i = 1 ; i <= m ; i++){
        for (int j = bl[i] ; j <= br[i] ; j++)
            if (a[j]) vis[i][a[j]] = 1;
        for (int j = 0 ; j <= V ; j++)
            for (int p = 0 ; p < mxb ; p++)
                if (((j >> p) & 1) && vis[i][j ^ (1 << p)]) vis[i][j] = 1;
    }
    for (int i = n ; i >= 1 ; i--) suf[i] = suf[i + 1] + (!a[i] ? mxb * i : 0);
    for (int i = 1 ; i <= n ; i++){
        LL ans = suf[i];
        for (int j = 0 ; j < mxb ; j++){
            int num = (1 << j);
            for (int p = i ; id[p] == id[i] ; p++)
                if (a[p] && !(num & a[p])) num |= a[p],ans += p;
            if (res[id[i]].count(num)){
                ans += res[id[i]][num];
                continue;
            }
            int z = num,ans2 = 0;
            for (int k = id[i] + 1 ; k <= m && num != V ; k++)
                if (vis[k][V ^ num])
                    for (int p = bl[k] ; p <= br[k] ; p++)
                        if (a[p] && !(num & a[p])) num |= a[p],ans2 += p;
            res[id[i]][z] = ans2; ans += ans2;
        }
        cout << ans << ' ';
    }
    cout << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    #endif 
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; //cin >> T;
    while (T--) solve();
    return 0;
}