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

Codeforces Round #1024(Div.1)

Div.2 B

题目大意：给定一个整数数组 $a_1, a_2, \ldots, a_n$。你可以执行以下操作任意次数（包括零次）： - 选择一个下标 $i$（$1 \le i \le n$）。将 $a_i$ 乘以 $-1$（即更新 $a_i := -a_i$）。需要判断是否可以通过上述操作使得下标为 $1$ 的元素成为数组的中位数。

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

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi tem;
    rep(i, 1, n - 1) tem.push_back(abs(a[i]));
    ranges::sort(tem);
    int tem2 = ranges::lower_bound(tem, abs(a[0])) - tem.begin();
    cout << (tem2 <= n / 2 ? "YES" : "NO") << endl;
    return;
}

Div.1 A

题目大意：你有一个 $n\times n$ 的网格，初始全部为空。你要把 $0$ 到 $n^2-1$ 这些数填入网格中，使得每个数出现恰好一次，并使这个网格的所有子网格的 mex 值之和最大。一个网格是另一个网格的子网格，当且仅当在后者中存在一个矩形区域和前者完全相同。\ 一个网格的 mex 最小的没有出现在此网格中的非负整数。

数据范围：$t(1\le t\le 100)$，$n(1\le n\le 500)$，$\sum n\le 1000$。

思路：

 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

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
void solve() {
    int n;
    cin >> n;
    vvi ma(n, vi(n, -1));
    int l, r;
    if (n % 2 == 1)
        l = r = n / 2;
    else
        l = r = n / 2 - 1;
    ma[l][r] = 0;
    int val = 1;
    int tem = 1;
    while (val < n * n) {
        rep(i, 0, 3) {
            rep(j, 1, tem) {
                l += dx[i], r += dy[i];
                if (l >= 0 && l <= n - 1 && r >= 0 && r <= n - 1 && ma[l][r] == -1) ma[l][r] = val++;
                if (val >= n * n) break;
            }
            if (val >= n * n) break;
            if (i % 2 == 1) tem++;
        }
    }
    rep(i, 0, n - 1) {
        rep(j, 0, n - 1) { cout << ma[i][j] << ' '; }
        cout << endl;
    }
    return;
}

Div.1 B

题目大意：给定一个长度为 $n$ 的排列 $a$ $^{\text{∗}}$。你可以进行以下操作任意次数（包括零次）： - 选择一个下标 $1 \le i \le n - 3$。然后，同时交换 $a_i$ 和 $a_{i+2}$，以及 $a_{i+1}$ 和 $a_{i+3}$。换句话说，排列 $a$ 将从 $[\ldots, a_i, a_{i+1}, a_{i+2}, a_{i+3}, \ldots]$ 变为 $[\ldots, a_{i+2}, a_{i+3}, a_i, a_{i+1}, \ldots]$。请确定通过任意次上述操作后能得到的字典序最小的排列 $^{\text{†}}$。

数据范围：$t(1\le t\le 1000)$，$n(4\le n\le 2\times 10^5)$，$a_1,a_2,\cdots,a_n(1\le a_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

template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi tem;
    vi tem2;
    rep(i, 0, n - 1) {
        if (i % 2 == 0)
            tem.push_back(a[i]);
        else
            tem2.push_back(a[i]);
    }
    ll tot = 0, tot2 = 0;
    int m1 = sz(tem), m2 = sz(tem2);
    int cnt = 0, cnt2 = 0;
    Tree tree1(2 * n), tree2(2 * n);
    auto sorted1 = tem, sorted2 = tem2;
    frep(i, m1 - 1, 0) {
        ll tem3 = tree1.query(0, tem[i] - 1);
        tot += tem3;
        tree1.add(tem[i], 1);
    }
    frep(i, m2 - 1, 0) {
        ll tem4 = tree2.query(0, tem2[i] - 1);
        tot2 += tem4;
        tree2.add(tem2[i], 1);
    }
    if (tot % 2 == tot2 % 2) {
        ranges::sort(tem);
        ranges::sort(tem2);
        rep(i, 0, n - 1) {
            if (i % 2 == 0)
                a[i] = tem[cnt++];
            else
                a[i] = tem2[cnt2++];
        }
    } else {
        ranges::sort(tem);
        ranges::sort(tem2);
        rep(i, 0, n - 1) {
            if (i % 2 == 0)
                a[i] = tem[cnt++];
            else
                a[i] = tem2[cnt2++];
        }
        swap(a[n - 1], a[n - 3]);
    }
    rep(i, 0, n - 1) cout << a[i] << ' ';
    cout << endl;
    return;
}

Div.1 C

题目大意：我们定义 $d_x(c)$ 为整数 $x$ 在数列 $c$ 中的距离，也就是 $c$ 中出现的两个 $x$ 之间的最长间隔。若 $x$ 出现的次数不足两次则为零。形式化地，$d_x(c)=\max\limits_{1\le i

数据范围：$t(1\le t\le 10^4)$，$n(1\le n\le 2\times 10^5)$，$a_1,a_2,\cdots,a_n(1\le a_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

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl pre(n);
    vl suf(n + 1);
    set<int> s;
    rep(i, 1, n) s.insert(i);
    int cnt = 0;
    rep(i, 0, n - 1) {
        auto it = s.upper_bound(a[i]);
        if (it != s.begin()) {
            it--;
            s.erase(s.find(*it));
            cnt++;
        }
        pre[i] = cnt;
    }
    s.clear();
    cnt = 0;
    rep(i, 1, n) s.insert(i);
    frep(i, n - 1, 0) {
        auto it = s.upper_bound(a[i]);
        if (it != s.begin()) {
            it--;
            s.erase(s.find(*it));
            cnt++;
        }
        suf[i] = cnt;
    }
    ll ans = 0;
    rep(i, 0, n - 1) ans += min(pre[i], suf[i + 1]);
    cout << ans << endl;
    return;
}

Div.1 D

题目大意：一个长度为 $|b|$ 的数组 $b$ 被称为"可爱的"，当且仅当其最长递增子序列（LIS）的长度与最长递减子序列（LDS）的长度 $^{\text{∗}}$ 之和恰好比数组长度大 1。更正式地说，数组 $b$ 是可爱的当且仅当 $\operatorname{LIS}(b) + \operatorname{LDS}(b) = |b| + 1$。给定一个长度为 $n$ 的排列 $a$ $^{\text{†}}$。需要统计排列 $a$ 中所有非空子数组 $^{\text{‡}}$ 中满足可爱条件的数量。

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

struct Info {
    ll x;
    Info(ll x = -2) : x(x) {}
};
Info operator+(const Info& a, const Info& b) {
    Info c;
    c.x = max(a.x, b.x);
    return c;
}
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a + b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }
    // 若固定左端点，需要记录前缀分段最大值，并加被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    // 传入一个数组维护
    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    // 查询[ql,qr]中第一个满足条件的下标
    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }

    // 查询[ql,qr]中最后一个满足条件的下标
    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }
};
class LazySegmentTree {
private:
    struct Node {
        int l, r;
        int min_cover_len = 0;  // 区间内被覆盖的最小次数
        int min_cover = 0;      // 区间内为最小次数的区间长度
        int todo = 0;           // 懒标记
    };

    vector<Node> seg;

    void maintain(int o) {
        Node& lo = seg[o << 1];
        Node& ro = seg[(o << 1) | 1];
        int mn = min(lo.min_cover, ro.min_cover);
        seg[o].min_cover = mn;
        seg[o].min_cover_len = (lo.min_cover == mn ? lo.min_cover_len : 0) + (ro.min_cover == mn ? ro.min_cover_len : 0);
    }  // 根据左右儿子的信息，更新当前节点的信息

    void do_(int o, int v) {
        seg[o].min_cover += v;
        seg[o].todo += v;
    }  // 仅更新节点信息，不下传懒标记

    void pushdown(int o) {
        int& v = seg[o].todo;
        if (v) {
            do_(o << 1, v);
            do_(o << 1 | 1, v);
            v = 0;
        }
    }  // 下传懒标记

    void build(vi& xs, int o, int l, int r) {
        seg[o].l = l;
        seg[o].r = r;
        if (l == r) {
            seg[o].min_cover_len = xs[l + 1] - xs[l];
            return;
        }
        int m = (l + r) >> 1;
        build(xs, o << 1, l, m);
        build(xs, o << 1 | 1, m + 1, r);
        maintain(o);
        return;
    }

    void update(int o, int l, int r, int v) {
        if (l <= seg[o].l && seg[o].r <= r) {
            do_(o, v);
            return;
        }
        pushdown(o);
        int m = (seg[o].l + seg[o].r) >> 1;
        if (l <= m) update(o << 1, l, r, v);
        if (m < r) update(o << 1 | 1, l, r, v);
        maintain(o);
    }

public:
    LazySegmentTree(vi& xs) {
        unsigned n = sz(xs) - 1;  // 有这么多个差值
        seg.resize(2 << bit_width(n - 1));
        build(xs, 1, 0, n - 1);  // 根节点是1
    }

    void update(int l, int r, int v) { update(1, l, r, v); }

    int get_uncovered_length() { return seg[1].min_cover ? 0 : seg[1].min_cover_len; }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    SegmentTree<Info> tree(n + 1, Info(-1));
    vl l(n);
    vl r(n);
    rep(i, 1, n - 1) {
        l[i] = l[i - 1];
        if (i >= 2) tree.update(a[i - 2], Info(i - 2));
        int tem = min(a[i], a[i - 1]) + 1;
        int tem2 = max(a[i], a[i - 1]) - 1;
        if (tem > tem2) continue;
        int tem3 = tree.query(tem, tem2).x;
        l[i] = max(1LL * tem3 + 1, l[i]);
    }
    SegmentTree<Info> tree2(n + 1, Info(-INT_MAX));
    r[n - 1] = n - 1;
    frep(i, n - 2, 0) {
        r[i] = r[i + 1];
        if (i <= n - 3) tree2.update(a[i + 2], Info(-(i + 2)));
        int tem = min(a[i], a[i + 1]) + 1;
        int tem2 = max(a[i], a[i + 1]) - 1;
        if (tem > tem2) continue;
        int tem3 = -tree2.query(tem, tem2).x;
        r[i] = min(1LL * tem3 - 1, r[i]);
    }
    struct Event {
        int y, lx, rx, d;
    };
    vector<Event> events;
    vi xs;
    rep(i, 0, n - 1) {
        xs.push_back(l[i]);
        xs.push_back(i + 1);
        events.emplace_back(i, l[i], i + 1, 1);
        events.emplace_back(r[i] + 1, l[i], i + 1, -1);
    }
    ranges::sort(xs);
    xs.erase(unique(all(xs)), xs.end());
    sort(all(events), [&](const Event& a, const Event& b) { return a.y < b.y; });
    LazySegmentTree tree3(xs);
    ll ans = 0;
    rep(i, 0, sz(events) - 2) {
        auto [y, lx, rx, d] = events[i];
        int L = ranges::lower_bound(xs, lx) - xs.begin();
        int R = ranges::lower_bound(xs, rx) - xs.begin() - 1;
        tree3.update(L, R, d);
        int height = events[i + 1].y - y;
        int width = xs.back() - xs[0] - tree3.get_uncovered_length();
        ans += 1LL * height * width;
    }
    cout << ans << endl;
    return;
}