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 <bits/stdc++.h>
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;
}