「CF1930F」Maximize the Difference

发表于 分类于 本文字数： 1.7k 阅读时长 ≈ 2 分钟

Description

Link：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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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;
}