「CF1930F」Maximize the Difference

    「CF1930F」Maximize the Difference

    CF1930F

    对于一个长度为 mm 的非负数组 bb,定义 f(b)f(b) 等于

    max⁡x≥0{max⁡i=1m(bi∣⁡x)−min⁡i=1m(bi∣⁡x)}\max_{x\geq 0}\left\{ \max_{i = 1}^m(b_i \operatorname{|} x) - \min_{i = 1}^m(b_i \operatorname{|} x) \right\}

    给出值域上限 nn 以及操作次数 QQ,初始时数组 aa 为空,有 QQ 次强制在线的操作:每次操作在数组 aa 的末尾加入一个数 vv (0≤v<n0 \leq v < n),你需要求出此时的 f(a)f(a)。

    数据范围:1≤n≤2221 \leq n \leq 2^{22},1≤Q≤1061 \leq Q \leq 10^6。

    时空限制:33s / 256256MiB。

    Solution

    不妨先求出,对于任意非负整数 p,qp, q 的 max⁡x≥0{(p∣⁡x)−(q∣⁡x)}\max\limits_{x\geq 0}\left\{ (p \operatorname{|} x) - (q \operatorname{|} x) \right\}。发现二进制下的每一位是独立的,对于某一位,只有 p,qp, q 在这一位上分别为 1,01, 0 时才有贡献。

    于是上式的值,可以被表示为 (p∣⁡q)−q(p \operatorname{|} q) - q,也可以被表示为 p−(p&⁡q)p - (p \operatorname{\&} q)。

    注意到原式的最大化极差可以放宽为最大化任意两个数的差,即

    max⁡x≥0max⁡1≤i,j≤m{(bi∣⁡x)−(bj∣⁡x)}max⁡1≤i,j≤mmax⁡x≥0{(bi∣⁡x)−(bj∣⁡x)}max⁡1≤i,j≤m{(bi∣⁡bj)−bj}\max_{x\geq 0}\max_{1 \leq i, j \leq m} \left\{ (b_i \operatorname{|} x) - (b_j \operatorname{|} x) \right\} \\ \max_{1 \leq i, j \leq m}\max_{x\geq 0} \left\{ (b_i \operatorname{|} x) - (b_j \operatorname{|} x) \right\} \\ \max_{1 \leq i, j \leq m} \left\{ (b_i \operatorname{|} b_j) - b_j \right\}

    考虑新加入一个数 vv 对于 f(a)f(a) 的影响,当其作为 bjb_j 的时候,式子为 (bi∣⁡bj)−bj(b_i \operatorname{|} b_j) - b_j,相当于要最大化 bi∣⁡vb_i \operatorname{|} v。

    记一个数组 f[u] 表示是否有一个数的子集为 uu。首先 vv 中已经为 11 的那些位就可以不用管了,剩余的位可以从高到低位贪心,根据 f 数组来判断是否可以扩展这一位。

    至于 f 数组的更新,可以使用类似 2025 ICPC 南京站 F 的方式,每次更改一个位地往下记忆化搜索。

    当其作为 bib_i 的时候,式子为 bi−(bi&⁡bj)b_i - (b_i \operatorname{\&} b_j),相当于要最小化 bj&⁡vb_j \operatorname{\&} v,这是一个对称的问题。

    时间复杂度 O(nlog⁡n+Qlog⁡n)\mathcal{O}(n \log n + Q \log n)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int M = 1 << 22;
    
    int n, Q, m;
    int f[M]; // f[u]:是否有数的子集为 u
    int g[M]; // g[u]:是否有数的超集为 u
    
    void addf(int u) {
        if (f[u]) {
            return;
        }
        f[u] = 1;
        for (int i = 0; i < m; i ++) {
            if (u >> i & 1) {
                addf(u ^ (1 << i));
            }
        }
    }
    int askOr(int u) {
        int v = 0;
        for (int i = m - 1; i >= 0; i --) {
            if (!(u >> i & 1) && f[v ^ (1 << i)]) {
                v ^= (1 << i);
            }
        }
        return v | u;
    }
    
    void addg(int u) {
        if (u >= (1 << m) || g[u]) {
            return;
        }
        g[u] = 1;
        for (int i = 0; i < m; i ++) {
            if (!(u >> i & 1)) {
                addg(u ^ (1 << i));
            }
        }
    }
    int askAnd(int u) {
        int v = (1 << m) - 1;
        for (int i = m - 1; i >= 0; i --) {
            if ((u >> i & 1) && g[v ^ (1 << i)]) {
                v ^= (1 << i);
            }
        }
        return v & u;
    }
    
    void work() {
        std::cin >> n >> Q;
    
        m = 1;
        while ((1 << m) < n) {
            m ++;
        }
    
        int lastans = 0;
        for (int i = 1; i <= Q; i ++) {
            int u;
            std::cin >> u;
            u = (u + lastans) % n;
    
            chmax(lastans, askOr(u) - u);
            addf(u);
    
            chmax(lastans, u - askAnd(u));
            addg(u);
    
            std::cout << lastans << ' ';
        }
        std::cout << '\n';
    
        for (int i = 0; i < (1 << m); i ++) {
            f[i] = g[i] = 0;
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }