题解：P12555 [UOI 2024] AND Array

· · 题解

每次都要扫一个后缀，考虑直接倒着做。

考虑如何计算一个 f(i,j)。不妨设 m 表示 2^b-1 抠掉 j 那一位剩下的部分，可以发现第一次我们总要跳到一个满足 a_i 是 m 的子集的那些数中下标最小的位置，然后使 m\gets m-a_i，抠掉之后是在新的后缀做子问题。显然，在把 a_i=0 特殊处理后，这个子问题最多做 b 次就会使得 m 变为 0，或者不存在能跳到的位置。

考虑这个子问题具有不合法不优的性质：我们无需考虑从 i 跳到一个位置 i' 之后不能跳到 [i,i') 中的位置这一限制。因为若在 [i,i') 存在满足条件的位置，则 i 不可能先跳到 i'。这意味着我们在 i' 也可以利用 i 的信息。

考虑把刚刚那个问题形式化：我们寻找跳的位置本质上是在求子集 \min，移动后缀本质上是在单点修改（插入 (a_i,i)）。根据不合法不优的性质，我们无需持久化这个数据结构，因为每次在计算 f(i,j) 的过程中跳跃都只需查询 i 处后缀的信息。

直接做可以做到 \mathcal O(nb^22^b)，常数很小可以轻松获得 40 分。

考虑我们现在是一边查询 \mathcal O(2^b)，一边修改 \mathcal O(1)，这样很不好。考虑 trick from [CTSC2017] 吉夫特，我们实际上可以把二进制掰成两半，定义 f_{u,v} 表示二进制左半部分是 u 的子集，右半部分是 v 的那些数的 \min，那么我们修改时只需枚举左侧的超集，查询时只需枚举右侧的子集，就可以平衡了。

直接分成两半可以做到 \mathcal O(nb^2\sqrt {2^b})，但是显然不够平衡，因为我们一共有 \mathcal O(nb^2) 次查询，但只有 \mathcal O(n) 次修改。调至 15+5 两者几乎平衡，但由于 cache miss 等原因，常数较大的时限仍然会 TLE。不过 13+7 时就可以轻松通过了。

int n,b;
int a[N];
int f[25];
int dp[1<<13][1<<7];
ll ans[N];
ll sum0;
int bl;
il int getf(int msk){
    int cu=msk&((1<<bl)-1);
    int minn=1e9;
    for(int j=cu;;j=(j-1)&cu){
        minn=min(minn,dp[msk>>bl][j]);
        if(!j) break;
    }
    return minn;
}
// #define Shun cute
int main(){
#ifdef Shun
    freopen("P12555_6.in","r",stdin);
    freopen("ext.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>b;
    fr1(i,1,n) cin>>a[i];
    bl=min(b,7);
    memset(dp,0x3f,sizeof dp);
    fr2(i,n,1){
        fr1(j,0,b-1){
            if(!((a[i]>>j)&1)){
                ll sum=i;
                int msk=(1<<b)-1-a[i]-(1<<j);
                int id;
                while((id=getf(msk))<=n){
                    sum+=id;
                    msk-=a[id];
                }
                f[j]=sum+sum0;
            }
        }
        fr1(j,0,b-1) ans[i]+=f[j];
        if(a[i]){
            int fix=a[i]&((1<<bl)-1);
            int oth=(a[i]>>bl);
            int msk=(1<<b-bl)-1-(a[i]>>bl);
            for(int j=msk;;j=(j-1)&msk){
                dp[j|oth][fix]=min(dp[j|oth][fix],i);
                if(!j) break;
            }
        }
        else sum0+=i;
    }
    fr1(i,1,n) cout<<ans[i]<<' ';
    ET;
}
//ALL FOR Zhang Junhao.