Codeforces Round #1054(Div.3)

D

题目大意：给定一个长度为 $n$ 的字符串 $s$，仅由字符 ‘a’ 和 ‘b’ 组成。每次操作，你可以选择一个位置 $i$（$1 \le i \le n-1$），交换相邻的字符 $s_i$ 和 $s_{i+1}$。需要用最少的操作次数，使得同一种字符（‘a’ 或 ‘b’）全部连续地排列在一起，形成恰好一个连续的块。另一种字符可以在这个块的前面或后面，形成最多两个（可能为空）的块。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \times 10^5$，$\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
void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = LLONG_MAX;
    vl tem;
    rep(i, 0, n - 1) {
        if (s[i] == 'a') tem.push_back(i - sz(tem));
    }
    if (sz(tem) <= 1 || sz(tem) >= n - 1) {
        cout << 0 << endl;
        return;
    }
    ll m1 = sz(tem);
    vl pre(m1 + 1);
    rep(i, 0, m1 - 1) pre[i + 1] = pre[i] + tem[i];
    ans = min(ans, pre[m1] - pre[m1 / 2 + 1] - tem[m1 / 2] * (m1 - m1 / 2 - 1) + tem[m1 / 2] * (m1 / 2) - pre[m1 / 2]);
    vl tem2;
    rep(i, 0, n - 1) {
        if (s[i] == 'b') tem2.push_back(i - sz(tem2));
    }
    ll m2 = sz(tem2);
    vl pre2(m2 + 1);
    rep(i, 0, m2 - 1) pre2[i + 1] = pre2[i] + tem2[i];
    ans = min(ans, pre2[m2] - pre2[m2 / 2 + 1] - tem2[m2 / 2] * (m2 - m2 / 2 - 1) + tem2[m2 / 2] * (m2 / 2) - pre2[m2 / 2]);
    cout << ans << endl;
    return;
}

E

题目大意：在 Deepwoken 的世界中，存在着一件古老的神器——无限知识石板，上面刻有一串由 $n$ 个神秘符号组成的序列（每个符号为一个整数）。传说，只有找到所有的神圣碎片，才能揭示神器真正的力量——神圣碎片指的是石板上所有正好包含 $k$ 个不同数字的连续片段，且它们的长度要在 $l$ 到 $r$ 之间（包含 $l$ 和 $r$）。

数据范围：$1 \leq t \leq 10^4$，$1 \leq k \leq n \leq 2 \cdot 10^5, 1 \leq l \leq r \leq n$，$1 \leq a_i \leq 10^9$，$\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
void solve() {
    ll n, k, l, r;
    cin >> n >> k >> l >> r;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll l1 = 0, l2 = 0;
    map<ll, ll> ma;
    ll ans = 0, ans2 = 0;
    rep(r1, 0, n - 1) {
        ma[a[r1]]++;
        while (sz(ma) > k) {
            if (--ma[a[l1]] == 0) ma.erase(ma.find(a[l1]));
            l1++;
        }
        ll tem = max(l1, r1 - r + 1);
        ll tem2 = r1 - l + 1;
        if (tem <= tem2) ans += tem2 - tem + 1;
    }
    ma.clear();
    rep(r2, 0, n - 1) {
        ma[a[r2]]++;
        while (sz(ma) > k - 1) {
            if (--ma[a[l2]] == 0) ma.erase(ma.find(a[l2]));
            l2++;
        }
        ll tem = max(l2, r2 - r + 1);
        ll tem2 = r2 - l + 1;
        if (tem <= tem2) ans2 += tem2 - tem + 1;
    }
    cout << ans - ans2 << endl;
    return;
}

F

题目大意：祢豆子突然醒来，发现自己处在数轴上的 $0$ 点，并且拥有 $h$ 点生命值。她想要到达 $d$ 点。在每一回合中，她可以选择以下两种操作之一： - 在树荫下休息，使她当前的生命值增加 $1$； - 从当前位置 $x$ 移动到 $x+1$。每次移动都会消耗祢豆子的生命值；如果这是连续第 $j$ 次移动，则她的生命值会减少 $j$ 点。如果在某次移动后她的生命值降到 $0$ 或以下，则无法进行这次移动。此时她在 $1$ 点，生命值为 $6$。2. 从 $1$ 移动到 $2$，生命值减少 $2$。此时她在 $2$ 点，生命值为 $4$。3. 从 $2$ 移动到 $3$，生命值减少 $3$。此时她在 $3$ 点，生命值为 $1$。

数据范围：$1 \le t \le 10^4$，$1\le h,d \le 10^9$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    ll h, d;
    cin >> h >> d;
    ll l = 0, r = 1e18, mid, ans = -1;
    auto check = [&](ll mid) -> bool {
        ll tot = d / (mid + 1);
        ll re = d % (mid + 1);
        return re * (tot + 1) * (tot + 2) / 2 + (mid + 1 - re) * (tot + 1) * tot / 2 <= h + mid - 1;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans + d << endl;
    return;
}

G

题目大意：在残酷的 Blue Lock 世界中，Buratsuta 3 是被选中推翻现任冠军并带领日本 U-20 队走向荣耀的三人组合。Sae Itoshi 已经锁定了首席席位，剩余两个名额将在激烈的 Side-B 选拔中角逐。为了考察候选人的战略能力，Buratsuta 给定了如下挑战：给定一个长度为 $n$ 的整数数组“表现记录”以及 $q$ 个查询。每个查询指定了一个子数组 $[l, r]$。在该子数组中，找出所有出现次数严格大于 $\lfloor\frac{r - l + 1}{3}\rfloor$ 的记录值。

数据范围：$1 \le t \le 10^4$，$1 \le n, q \le 2 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le l \le r \le n$，$\sum n \le 2 \times 10^5$，$\sum q \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
struct ChairmanTree {
    struct Node {
        int ls = 0, rs = 0, cnt = 0;
    };

    vector<Node> tr;
    vector<int> root;
    vector<ll> vals;

    ChairmanTree(const vector<ll>& a) {
        vals = a;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        int n = a.size();

        tr.reserve((n + 1) * 20);
        tr.push_back(Node());

        root.assign(n + 1, 0);
        root[0] = 0;

        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(vals.begin(), vals.end(), a[i - 1]) - vals.begin() + 1;
            root[i] = add(root[i - 1], 1, vals.size(), pos);
        }
    }

    int add(int old, int l, int r, int p) {
        int o = copy_node(old);
        tr[o].cnt++;

        if (l == r) return o;

        int m = (l + r) >> 1;

        if (p <= m)
            tr[o].ls = add(tr[old].ls, l, m, p);
        else
            tr[o].rs = add(tr[old].rs, m + 1, r, p);

        return o;
    }

    ll kth(int l, int r, int k) const {
        return vals[kth(root[l - 1], root[r], 1, vals.size(), k) - 1];
    }

    ll leq(int l, int r, ll x) const {
        int pos = upper_bound(vals.begin(), vals.end(), x) - vals.begin();

        if (!pos) return 0;

        return query(root[l - 1], root[r], 1, vals.size(), pos);
    }

private:
    int copy_node(int old) {
        tr.push_back(tr[old]);
        return tr.size() - 1;
    }

    int kth(int old, int now, int l, int r, int k) const {
        if (l == r) return l;

        int left_cnt = tr[tr[now].ls].cnt - tr[tr[old].ls].cnt;
        int m = (l + r) >> 1;

        if (k <= left_cnt)
            return kth(tr[old].ls, tr[now].ls, l, m, k);

        return kth(tr[old].rs, tr[now].rs, m + 1, r, k - left_cnt);
    }

    ll query(int old, int now, int l, int r, int qr) const {
        if (r <= qr) return tr[now].cnt - tr[old].cnt;

        int m = (l + r) >> 1;

        ll res = query(tr[old].ls, tr[now].ls, l, m, qr);

        if (qr > m) {
            res += query(tr[old].rs, tr[now].rs, m + 1, r, qr);
        }

        return res;
    }
};

// 使用：ChairmanTree ct(a);
// ct.kth(l, r, k)：查询 1-indexed 区间 [l, r] 第 k 小的原值
// ct.leq(l, r, x)：查询区间 [l, r] 内 <= x 的数量和总和
//
// vector<ll> a(n);               // a 是 0-indexed 原数组
// ChairmanTree ct(a);
// ll kth_val = ct.kth(l, r, k);  // l, r, k 都按 1-indexed 传
// auto [cnt, sum] = ct.leq(l, r, limit);
void solve() {
    ll n, q, x, y;
    cin >> n >> q;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ChairmanTree ct(a);
    rep(i, 0, q - 1) {
        cin >> x >> y;
        ll l = y - x + 1;
        ll tem = l / 3 + 1;
        ll tem2 = l * 2 / 3 + 1;
        vl res;
        res.push_back(ct.kth(x, y, tem));
        res.push_back(ct.kth(x, y, tem2));
        if (res[0] == res[1]) {
            ll cnt = ct.leq(x, y, res[0]) - ct.leq(x, y, res[0] - 1);
            if (cnt > l / 3)
                cout << res[0] << endl;
            else
                cout << -1 << endl;
            continue;
        }
        vl res2;
        ll cnt = ct.leq(x, y, res[0]) - ct.leq(x, y, res[0] - 1);
        ll cnt2 = ct.leq(x, y, res[1]) - ct.leq(x, y, res[1] - 1);
        if (cnt > l / 3) res2.push_back(res[0]);
        if (cnt2 > l / 3) res2.push_back(res[1]);
        if (res2.empty())
            cout << -1 << endl;
        else {
            ranges::sort(res2);
            for (auto& p : res2) cout << p << ' ';
            cout << endl;
        }
    }
    return;
}