AtCoder ABC324G 启发式合并

题意

传送门 AtCoder ABC324G Generate Arrays

题解

逆则操作顺序考虑，可以看作至多 $n$ 个联通分量不断合并的过程，此时使用启发式合并，即规模较小的连通分量向规模较大的连通分量合并，以单个元素合并为基本运算，则基本运算次数为 $O(n\log n)$。

使用 std::set 分别维护以索引和值为关键字的集合，每次分裂出较小的分量即可。关于如何计算出所分裂两个分量的规模的问题，对于以索引为关键字的平衡树，操作直接给出了右侧元素的相对位置 $x_i$，则规模可以直接计算；而对于以值为关键字的平衡树，操作仅给出了需要大于的值 $x_i$，此时平衡树无法直接计算相对位置，那么可以二分出第一个满足 $val>x_i$ 的位置，使用两个迭代器分别不断左右移动直到边界，则在操作数限制为较小分量规模大小的约束下，计算出了分裂的两个分量的规模。总时间复杂度 $O(n{\log }^{2}n)$。

#include 
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    using pst = set<pair<int, int>>;
    vector<pst> pos(q + 1), val(q + 1);
    for (int i = 0; i < n; ++i) {
        pos[0].insert({i, a[i]});
        val[0].insert({a[i], i});
    }
    for (int i = 1; i <= q; ++i) {
        int t, s, x;
        cin >> t >> s >> x;
        auto change = [](int a, int b, pst &_pos, pst &_val, pst &pos, pst &val) {
            if (a > b) {
                for (int j = 0; j < b; ++j) {
                    auto [k, a] = *prev(_pos.end());
                    _pos.erase({k, a});
                    _val.erase({a, k});
                    pos.insert({k, a});
                    val.insert({a, k});
                }
            } else {
                swap(_pos, pos);
                swap(_val, val);
                for (int j = 0; j < a; ++j) {
                    auto [k, a] = *pos.begin();
                    pos.erase({k, a});
                    val.erase({a, k});
                    _pos.insert({k, a});
                    _val.insert({a, k});
                }
            }
        };
        auto &_pos = pos[s];
        auto &_val = val[s];
        int a = -1, b = -1;
        if (t == 1) {
            int _n = _pos.size();
            if (x < _n) {
                a = x, b = _n - x;
            } else {
                a = _n, b = 0;
            }
            change(a, b, _pos, _val, pos[i], val[i]);
        } else {
            int _n = _val.size();
            auto it = _val.upper_bound({x, 1e9});
            if (it == _val.end()) {
                a = _n, b = 0;
            } else if (it == _val.begin()) {
                a = 0, b = _n;
            } else {
                a = b = 0;
                auto it2 = prev(it);
                for (;;) {
                    a += 1;
                    b += 1;
                    if (it2 == _val.begin()) {
                        b += _n - 2 * a;
                        break;
                    }
                    it2 = prev(it2);
                    it = next(it);
                    if (it == _val.end()) {
                        a += _n - 2 * a;
                        break;
                    }
                }
            }
            change(a, b, _val, _pos, val[i], pos[i]);
        }
        cout << (int)pos[i].size() << '\n';
    }

    return 0;
}
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