CF1903D2 Maximum And Queries (hard version)

· · 题解

这个题很会创人啊。经典 \rm D 难于 \rm E。

首先一眼贪心，设当前正在确定答案第 i 位为 0 还是 1。而所有数可以分为 2 类，第一类数是在之前因为 ans 的变化被迫与其贴齐，那么它的低 i 位必然全部为 0，造成的代价为 2^i；第二类数则是之前完全没有变过，也即 ans 是其高位的子集，如果这类数一共有 f_i 个，其低 i 位总和为 g_i，那么代价就是 f_i\times 2^i-g_i。

瓶颈在于求出每次贪心的 f 和 g。注意到这类数需要满足高位在 ans 对应的位置上有，而在第 i 位上没有。预处理的时候枚举 i，针对那些第 i 位为 0 的数，处理出数列 \displaystyle A_i=\sum_{i\subseteq j}1,B_i=\sum_{i\subseteq j}v_j，其中 v_j 是 a_j 低 i 位的值。这个东西直接高维后缀和就好。

复杂度 O(V\log^2V+q\log V)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 1200005

int n,q,a[MAXN],f[20][MAXN],g[20][MAXN];

signed main(){
    scanf("%lld%lld",&n,&q); int S = 0;
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]),S += ( 1 << 20 ) - a[i];
    for( int p = 19 ; p >= 0 ; p -- ){
        for( int j = 1 ; j <= n ; j ++ ) if( !( a[j] >> p & 1 ) ) f[p][a[j]] ++,g[p][a[j]] += a[j] & ( ( 1 << p ) - 1 );
        for( int k = 0 ; k <= 19 ; k ++ )
            for( int i = MAXN - 5 ; i >= 0 ; i -- )
                if( i & ( 1 << k ) ) f[p][i - ( 1 << k )] += f[p][i],g[p][i - ( 1 << k )] += g[p][i];
    }
    for( int i = 1 ; i <= q ; i ++ ){
        int k; scanf("%lld",&k);
        if( k >= S ){ printf("%lld\n",( 1 << 20 ) + ( k - S ) / n ); continue; }
        int res = 0,cat = 0;
        for( int p = 19 ; p >= 0 ; p -- ){
            int cost = cat * ( 1 << p ) + f[p][res] * ( 1 << p ) - g[p][res];
            if( k >= cost ) cat += f[p][res],res += 1 << p,k -= cost;
        }
        printf("%lld\n",res);
    }
    return 0;
}