Featured image of post Codeforces Round #1053(Div.1)

Codeforces Round #1053(Div.1)

Div.1 A

题目大意：⠀ 本题不允许使用 Hack。有一条包含 $10^9$ 个格子的带子，这些格子按 $1$ 到 $10^9$ 编号。每个格子可以是黑色或白色。起初，有 $m$ 个不同的格子 $a_1, a_2, \ldots, a_m$ 是黑色，其余的都是白色。如果有人当前位于格子 $x$，他可能会被给定以下两种指令之一： - $\texttt{A}$：跳到下一个格子，即格子 $x+1$； - $\texttt{B}$：跳到下一个白色格子，即最小的 $y > x$，满足格子 $y$ 是白色。

数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 10^5$，$1 \leq m \leq 10^5$，$1 \leq a_1 < a_2 < \ldots < a_m \leq 10^9$，$\sum n \le 10^5$，$\sum m \le 10^5$。

思路：

 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

using i128 = __int128_t;
void solve() {
    ll n, m;
    string s;
    cin >> n >> m >> s;
    vl a(m);
    rep(i, 0, m - 1) cin >> a[i];
    set<ll> s1;
    rep(i, 0, m - 1) s1.insert(a[i]);
    int cur = 1;
    rep(i, 0, n - 1) {
        if (s[i] == 'A') {
            cur++;
            s1.insert(cur);
        } else {
            cur++;
            while (s1.count(cur)) cur++;
            s1.insert(cur);
            cur++;
            while (s1.count(cur)) cur++;
        }
    }
    cout << sz(s1) << endl;
    for (auto& p : s1) cout << p << ' ';
    cout << endl;
    return;
}

Div.1 B

题目大意：⠀ Alice 有一个 $n \times n$ 的网格。最开始，所有的格子都是白色的。Alice 想要涂黑一些格子，并需要满足某些属性。设 $(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$ 是被涂成黑色的格子。你会得到一个长度为 $n$ 的数组 $a$。下列条件必须被满足： - 对于每一行 $k$（$1 \le k \le n$），恰好有 $a_k$ 个不同的 $i$（$1 \le i \le m$）使得 $x_i = k$。

数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$0 \le a_i \le n$，$\sum n \le 2 \cdot 10^5$。

思路：

 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

using i128 = __int128_t;
const ll MOD = 998244353;
constexpr int MX = 2e5 + 5;
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 1;
    rep(i, (n + 1) / 2, n - 1) {
        if (a[i] != 0) {
            cout << 0 << endl;
            return;
        }
    }
    ll re = 0;
    frep(i, (n + 1) / 2 - 1, 0) {
        re += 1 + (!(n % 2 == 1 && i == (n + 1) / 2 - 1));
        if (a[i] > re) {
            cout << 0 << endl;
            return;
        }
        ans = mul(ans, comb(re, a[i]));
        re -= a[i];
    }
    if (re != 0)
        cout << 0 << endl;
    else
        cout << ans << endl;
    return;
}

Div.1 C

题目大意：⠀ 有一家商店，共有 $n$ 件物品，编号为 $1$ 到 $n$，每种物品都只有一件。你认为每件物品的价值分别是 $v_1, v_2, \ldots, v_n$（其中价值可以为负数）。Alice 和 Bob 各自有自己喜欢的物品顺序（分别用 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$ 表示）。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \times 10^5$，$-10^9 \le v_i \le 10^9$，$1 \le a_i \le n$，$1 \le b_i \le n$，$\sum n \le 2 \times 10^5$。

思路：

  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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

using i128 = __int128_t;
struct Info {
    static constexpr ll INF = (1LL << 60);
    ll sum = 0;
    ll mx = -INF, se_mx = -INF;
    ll mn = INF, se_mn = INF;
    int cnt_mx = 0, cnt_mn = 0;
    ll add = 0;  // 只有区间加需要普通懒标记

    Info(ll x = 0) : sum(x), mx(x), se_mx(-INF), mn(x), se_mn(INF), cnt_mx(1), cnt_mn(1), add(0) {}
};

Info operator+(const Info& a, const Info& b) {
    Info c;
    c.sum = a.sum + b.sum;

    // 合并最大值、严格次大值、最大值个数
    if (a.mx == b.mx) {
        c.mx = a.mx;
        c.cnt_mx = a.cnt_mx + b.cnt_mx;
        c.se_mx = max(a.se_mx, b.se_mx);
    } else if (a.mx > b.mx) {
        c.mx = a.mx;
        c.cnt_mx = a.cnt_mx;
        c.se_mx = max(a.se_mx, b.mx);
    } else {
        c.mx = b.mx;
        c.cnt_mx = b.cnt_mx;
        c.se_mx = max(a.mx, b.se_mx);
    }

    // 合并最小值、严格次小值、最小值个数
    if (a.mn == b.mn) {
        c.mn = a.mn;
        c.cnt_mn = a.cnt_mn + b.cnt_mn;
        c.se_mn = min(a.se_mn, b.se_mn);
    } else if (a.mn < b.mn) {
        c.mn = a.mn;
        c.cnt_mn = a.cnt_mn;
        c.se_mn = min(a.se_mn, b.mn);
    } else {
        c.mn = b.mn;
        c.cnt_mn = b.cnt_mn;
        c.se_mn = min(a.mn, b.se_mn);
    }

    c.add = 0;
    return c;
}

class SegmentTreeBeats {
    int n;
    vector<Info> info;

    void maintain(int node) { info[node] = info[node << 1] + info[node << 1 | 1]; }  // 用左右儿子维护当前节点

    void build(const vector<Info>& a, int node, int l, int r) {
        if (l == r) {
            info[node] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(a, node << 1, l, m);
        build(a, node << 1 | 1, m + 1, r);
        maintain(node);
    }  // 建树，复杂度O(n)

    void apply_add(int node, int l, int r, ll x) {
        info[node].sum += x * (r - l + 1);
        info[node].mx += x;
        info[node].mn += x;
        if (info[node].se_mx != -Info::INF) info[node].se_mx += x;
        if (info[node].se_mn != Info::INF) info[node].se_mn += x;
        info[node].add += x;
    }  // 整段加x

    void apply_chmin(int node, ll x) {
        if (info[node].mx <= x) return;
        ll old = info[node].mx;
        info[node].sum += (x - old) * info[node].cnt_mx;
        if (info[node].mn == old) info[node].mn = x;
        if (info[node].se_mn == old) info[node].se_mn = x;
        info[node].mx = x;
    }  // 只把最大值压到x，要求se_mx < x < mx

    void apply_chmax(int node, ll x) {
        if (info[node].mn >= x) return;
        ll old = info[node].mn;
        info[node].sum += (x - old) * info[node].cnt_mn;
        if (info[node].mx == old) info[node].mx = x;
        if (info[node].se_mx == old) info[node].se_mx = x;
        info[node].mn = x;
    }  // 只把最小值抬到x，要求mn < x < se_mn

    void pushdown(int node, int l, int r) {
        if (l == r) {
            info[node].add = 0;
            return;
        }
        int m = (l + r) >> 1;
        if (info[node].add != 0) {
            apply_add(node << 1, l, m, info[node].add);
            apply_add(node << 1 | 1, m + 1, r, info[node].add);
            info[node].add = 0;
        }
        if (info[node << 1].mx > info[node].mx) apply_chmin(node << 1, info[node].mx);
        if (info[node << 1 | 1].mx > info[node].mx) apply_chmin(node << 1 | 1, info[node].mx);
        if (info[node << 1].mn < info[node].mn) apply_chmax(node << 1, info[node].mn);
        if (info[node << 1 | 1].mn < info[node].mn) apply_chmax(node << 1 | 1, info[node].mn);
    }  // 下传加法，并让儿子的min/max不越过当前节点

    void add(int node, int l, int r, int ql, int qr, ll x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply_add(node, l, r, x);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        add(node << 1, l, m, ql, qr, x);
        add(node << 1 | 1, m + 1, r, ql, qr, x);
        maintain(node);
    }  // 区间加[ql,qr]

    void chmin(int node, int l, int r, int ql, int qr, ll x) {
        if (qr < l || r < ql || info[node].mx <= x) return;
        if (ql <= l && r <= qr && info[node].se_mx < x) {
            apply_chmin(node, x);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        chmin(node << 1, l, m, ql, qr, x);
        chmin(node << 1 | 1, m + 1, r, ql, qr, x);
        maintain(node);
    }  // 区间取min：[ql,qr]内a[i]=min(a[i],x)

    void chmax(int node, int l, int r, int ql, int qr, ll x) {
        if (qr < l || r < ql || info[node].mn >= x) return;
        if (ql <= l && r <= qr && info[node].se_mn > x) {
            apply_chmax(node, x);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        chmax(node << 1, l, m, ql, qr, x);
        chmax(node << 1 | 1, m + 1, r, ql, qr, x);
        maintain(node);
    }  // 区间取max：[ql,qr]内a[i]=max(a[i],x)

    void assign(int node, int l, int r, int p, ll x) {
        if (l == r) {
            info[node] = Info(x);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (p <= m)
            assign(node << 1, l, m, p, x);
        else
            assign(node << 1 | 1, m + 1, r, p, x);
        maintain(node);
    }  // 单点赋值

    Info query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return info[node];
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (qr <= m) return query(node << 1, l, m, ql, qr);
        if (ql > m) return query(node << 1 | 1, m + 1, r, ql, qr);
        return query(node << 1, l, m, ql, qr) + query(node << 1 | 1, m + 1, r, ql, qr);
    }  // 区间查询[ql,qr]

public:
    SegmentTreeBeats(int n, Info init_val = Info()) : SegmentTreeBeats(vector<Info>(n, init_val)) {}

    SegmentTreeBeats(const vector<Info>& a) : n(sz(a)), info(2 << bit_width((unsigned)sz(a) - 1)) {
        build(a, 1, 0, n - 1);
    }  // 维护下标为[0,n-1]的数组

    void add(int ql, int qr, ll x) { add(1, 0, n - 1, ql, qr, x); }  // 区间加

    void chmin(int ql, int qr, ll x) { chmin(1, 0, n - 1, ql, qr, x); }  // 区间取min

    void chmax(int ql, int qr, ll x) { chmax(1, 0, n - 1, ql, qr, x); }  // 区间取max

    void assign(int p, ll x) { assign(1, 0, n - 1, p, x); }  // 单点赋值

    Info query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }  // 区间查询

    Info get(int p) { return query(p, p); }  // 单点查询

    ll sum(int ql, int qr) { return query(ql, qr).sum; }  // 区间和

    ll min_val(int ql, int qr) { return query(ql, qr).mn; }  // 区间最小值

    ll max_val(int ql, int qr) { return query(ql, qr).mx; }  // 区间最大值
};
void solve() {
    ll n;
    cin >> n;
    vl v(n + 1), a(n + 1), b(n + 1);
    rep(i, 1, n) cin >> v[i];
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i];
    vl p(n + 1);
    map<ll, ll> ma;
    rep(i, 1, n) ma[b[i]] = i;
    rep(i, 1, n) p[i] = ma[a[i]];
    vl w(n + 1);
    rep(i, 1, n) w[i] = v[a[i]];
    vector<Info> init(n + 1, Info(-(1LL << 60)));
    init[0] = Info(0);
    SegmentTreeBeats seg(init);
    rep(i, 1, n) {
        ll tem = seg.max_val(0, p[i] - 1);
        seg.add(0, p[i] - 1, w[i]);
        seg.chmax(p[i], p[i], tem);
    }
    cout << seg.max_val(0, n) << endl;
    return;
}