Featured image of post Codeforces Round #1104(Div.1+2)

Codeforces Round #1104(Div.1+2)

B

题目大意：Ja the Ghost 在玩橡皮鸭。他有 $n$ 堆橡皮鸭排成一排，第 $i$ 堆中有 $a_i$ 只鸭子。Quack the Duck 给 Ja 一个严格递增的序列 $b_1, b_2, \ldots, b_n$ 并命令他把这 $n$ 堆橡皮鸭变为这个序列。Ja 的操作过程分为两个阶段： 1. 他可以往每一堆中加入任意数量的鸭子。具体而言，对每一堆 $i$，他可以选择一个非负整数 $x_i$，将 $a_i$ 替换为 $a_i + x_i$。2. 他可以反复交换两堆相邻的橡皮鸭。具体而言，他可以进行如下操作若干次（可以为零次）：选择一个下标 $i$，其中 $1 \le i \le n-1$，交换 $a_i$ 和 $a_{i+1}$ 的值。

数据范围：$1 \le t \le 2000$，$1 \le n \le 2000$，$1 \le a_i \le 10^9$，$1 \le b_1 < b_2 < \cdots < b_n \le 10^9$，$\sum n \le 2000$。

思路：

 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

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n), b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vl pos(n);
    vl vis(n);
    vl c(n);
    rep(i, 0, n - 1) {
        int j = 0;
        while (j <= n - 1 && (vis[j] || b[j] < a[i])) {
            j++;
        }
        if (j == n) {
            cout << -1 << endl;
            return;
        }
        vis[j] = true;
        pos[i] = j;
        c[i] = b[j];
    }
    ll ans = 0;
    rep(i, 0, n - 1) {
        rep(j, i + 1, n - 1) { ans += (c[i] > c[j]); }
    }
    cout << ans << endl;
    return;
}

C

题目大意：Ja the Ghost 又开始玩橡胶鸭了！有 $n$ 堆橡胶鸭从左到右排成一行。初始时，第 $i$ 堆有 $a_i$ 只橡胶鸭。只要序列 $a$ 不是非递减序列，Ja 就必须进行如下操作： - 选择两个相邻的堆，且左边堆的鸭子比右边堆多。Ja 交换这两堆的位置，并且把新左边堆的鸭子数量加到新右边堆上。形式化地说，选择某个索引 $i$，满足 $1 \le i < n$ 且 $a_i > a_{i+1}$，然后用 $(a_i, a_{i+1})$ 替换为 $(a_{i+1}, a_i + a_{i+1})$。Ja 每次可以选择任意一个满足条件的下标 $i$。可以证明，无论他的选择如何，这一过程最终都会以序列变成非递减排列而结束。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$，$\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

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll l = 1, r = 1e18, mid, ans = 1;
    auto check = [&](ll mid) -> bool {
        if (a[0] > mid) return false;
        ll tem = a[0];
        rep(i, 1, n - 1) {
            if (tem > a[i])
                tem = a[i] + tem;
            else
                tem = a[i];
            if (tem > mid) return false;
        }
        return true;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return;
}

D

题目大意：一个二进制字符串是仅由字符 $0$ 和 $1$ 组成的字符串。字符 $0$ 和 $1$ 称为相反值。考虑一个二进制字符串 $t$，记 $|t|$ 为 $t$ 的长度。当 $|t| \ge 2$ 时，对于每个 $1 \le i < |t|$，字符 $t_i$ 和 $t_{i+1}$ 是相邻的。如果通过任意多次（也可以是零次）应用如下操作，能将二进制字符串 $t$ 归约为恰好长度为 $1$ 的字符串，则称 $t$ 是“美丽”的： - 选择一对相等的相邻字符，删去这两个字符，并在它们原位置插入一个相反值的字符。接着变为 $\mathtt{001}$，再变为 $\mathtt{11}$，最后是 $\mathtt{0}$。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^6$，$\sum n \le 10^6$。

思路：

 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

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vl ma(3);
    ll tem = 0;
    ma[0] = 1;
    ll ans = 0;
    rep(i, 0, n - 1) {
        tem += (s[i] == '0' ? 1 : -1);
        tem = (tem + 3) % 3;
        ans += 1LL * (i + 1) - ma[tem];
        ma[tem]++;
    }
    ll tem2 = 1;
    rep(i, 1, n - 1) {
        if (s[i] != s[i - 1]) {
            tem2++;
        } else {
            if (tem2 <= 2)
                tem2 = 1;
            else {
                if (tem2 % 2 == 0)
                    ans -= (tem2 / 2 - 1) * tem2 / 2;
                else
                    ans -= (tem2 / 2) * (tem2 / 2);
                tem2 = 1;
            }
        }
    }
    if (tem2 >= 3) {
        if (tem2 % 2 == 0)
            ans -= (tem2 / 2 - 1) * tem2 / 2;
        else
            ans -= (tem2 / 2) * (tem2 / 2);
    }
    cout << ans << endl;
    return;
}

E

题目大意：鸭子 Quack 拥有一个长度为 $n$ 的排列 $a$ 和一个未完成的序列 $b_1,b_2,\ldots,b_n$。序列 $b$ 中的每个元素要么等于 $-1$，要么是从 $1$ 到 $n$ 的整数。每个 $1$ 到 $n$ 的整数在 $b$ 中至多出现一次。Quack 希望把 $b$ 补全为一个与 $a$ 对易的排列。也就是说，在将 $b$ 中所有 $-1$ 替换后，对于每个 $1\le i\le n$，都应当满足 $a_{b_i}=b_{a_i}$。幽灵 Ja 想帮助 Quack。在所有补全 $b$ 的方案中，他希望找到字典序最小的一个。请判断这样的补全是否存在。

数据范围：$1\le t\le 10^4$，$1\le n\le 2 \times 10^5$，$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

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n), b(n);
    rep(i, 0, n - 1) cin >> a[i], a[i]--;
    rep(i, 0, n - 1) {
        cin >> b[i];
        if (b[i] != -1) b[i]--;
    }
    vl vis(n), fa(n), pos(n);
    vvl tem;
    int cnt = 0;
    rep(i, 0, n - 1) {
        if (vis[i]) continue;
        vl tem2;
        int cur = i;
        while (!vis[cur]) {
            vis[cur] = true;
            fa[cur] = cnt;
            pos[cur] = sz(tem2);
            tem2.push_back(cur);
            cur = a[cur];
        }
        tem.push_back(tem2);
        cnt++;
    }
    int m = sz(tem);
    vl id(m, -1), pos2(m, -1);
    rep(i, 0, n - 1) {
        if (b[i] == -1) continue;
        if (sz(tem[fa[i]]) != sz(tem[fa[b[i]]])) {
            cout << "NO" << endl;
            return;
        }
        int tem2 = (pos[b[i]] - pos[i] + sz(tem[fa[i]])) % sz(tem[fa[i]]);
        if (id[fa[i]] == -1) {
            id[fa[i]] = fa[b[i]];
            pos2[fa[i]] = tem2;
            continue;
        }
        if (id[fa[i]] != fa[b[i]] || tem2 != pos2[fa[i]]) {
            cout << "NO" << endl;
            return;
        }
    }
    vi vis2(m);
    rep(i, 0, m - 1) {
        if (id[i] == -1) continue;
        vis2[id[i]]++;
        if (vis2[id[i]] >= 2) {
            cout << "NO" << endl;
            return;
        }
    }
    vl mixx(m);
    vector<vector<pll>> tem2(n + 1);
    rep(i, 0, m - 1) {
        ll idx = -1, mixx2 = LLONG_MAX;
        rep(j, 0, sz(tem[i]) - 1) {
            if (tem[i][j] < mixx2) {
                idx = j;
                mixx2 = tem[i][j];
            }
        }
        mixx[i] = idx;
        if (!vis2[i]) tem2[sz(tem[i])].emplace_back(tem[i][idx], i);
    }
    vl cnt2(n + 1);
    rep(i, 1, n) { sort(all(tem2[i])); }
    rep(i, 0, n - 1) {
        if (id[fa[i]] != -1) continue;
        if (cnt2[sz(tem[fa[i]])] >= sz(tem2[sz(tem[fa[i]])])) {
            cout << "NO" << endl;
            return;
        }
        id[fa[i]] = tem2[sz(tem[fa[i]])][cnt2[sz(tem[fa[i]])]].second;
        pos2[fa[i]] = (mixx[tem2[sz(tem[fa[i]])][cnt2[sz(tem[fa[i]])]].second] - pos[i] + sz(tem[fa[i]])) % sz(tem[fa[i]]);
        cnt2[sz(tem[fa[i]])]++;
    }
    cout << "YES" << endl;
    vl res(n);
    rep(i, 0, m - 1) {
        rep(j, 0, sz(tem[i]) - 1) { res[tem[i][j]] = tem[id[i]][(j + pos2[i]) % sz(tem[i])]; }
    }
    rep(i, 0, n - 1) cout << res[i] + 1 << ' ';
    cout << endl;
    return;
}

F

题目大意：给定一个长度为 $n$ 的数组和一个固定整数 $m$。一次“涂色操作”定义如下： - 选择一个长度为 $m$ 的区间，并将其从左到右依次涂上数值 $1,2,\ldots,m$。形式上，选择一个整数 $l$，使得 $1\le l\le n-m+1$。然后对于每个 $1\le i\le m$，位置 $l+i-1$ 被涂上值 $i$。如果一个位置被多次涂色，则只有最后一次涂色的数值会保留。如果一个数组可以通过若干次涂色操作得到，并且每个位置至少被涂色一次，则称该数组为“合法”的。

数据范围：$1\le t\le 10^4$，$1\le m\le n\le 5\cdot 10^5$，$1\le a_i\le m$，$\sum n \le 5\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
 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
223
224

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, m;
    cin >> n >> m;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i], a[i]--;
    const ll INF = 1e15;
    vector<Info> init(n - m + 1, Info(INF));
    SegmentTreeBeats seg(init);
    rep(i, 0, n - 1) {
        ll l1 = max(0LL, i - m + 1), l2 = max(0LL, i - m);
        ll r1 = min(1LL * i, n - m), r2 = min(1LL * i - 1, n - m);
        if (i <= n - m) {
            if (i == 0)
                seg.chmin(i, i, 0);
            else if (l2 <= r2)
                seg.chmin(i, i, seg.min_val(l2, r2));
        }
        if (i >= m) {
            seg.chmin(l1, r1, seg.min_val(i - m, i - m));
        }
        seg.add(l1, r1, 1);
        if (l1 <= i - a[i] && i - a[i] <= r1) seg.add(i - a[i], i - a[i], -1);
    }
    cout << seg.min_val(n - m, n - m) << endl;
    return;
}