更神奇了，改成 `std::set` 甚至都能过。。。
by lcyxds @ 2024-03-24 03:03:24
```cpp
#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;
int n;
int m;
struct Node {
int val;
int p = 0;
set<pair<int, int>> curQue;
};
vector<Node> nodes;
int P(int a) {
if (nodes[a].p == a) {
return a;
}
return nodes[a].p = P(nodes[a].p);
}
void AddTo(set<pair<int, int>>& a, set<pair<int, int>>& b) {
if (b.size() < a.size()) {
swap(a, b);
}
b.insert(a.begin(), a.end());
a.clear();
}
int Merge(int a, int b) {
// cout << a << ',' << b << ' ';
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
if (nodes[a].val < nodes[b].val || nodes[a].val == nodes[b].val && a < b) {
swap(a, b);
}
AddTo(nodes[a].curQue, nodes[b].curQue);
return b;
}
void MergeAio(int a, int b) {
if (nodes[a].val == -1 || nodes[b].val == -1) {
return;
}
a = P(a);
b = P(b);
if (a == 0 || b == 0 || a == b) {
return;
}
if (nodes[a].val < nodes[b].val || nodes[a].val == nodes[b].val && a < b) {
swap(a, b);
}
nodes[a].p = b;
Merge(a, b);
}
int Delete(int a) {
if (nodes[a].val == -1) {
return -1;
}
a = P(a);
nodes[a].curQue.erase(nodes[a].curQue.begin());
// cout << "sz=" << nodes[a].curQue.size() << endl;
if (nodes[a].curQue.size()) {
int newRoot = nodes[a].curQue.begin()->second;
// cout << a << ',' << newRoot << endl;
swap(nodes[a].curQue, nodes[newRoot].curQue);
nodes[newRoot].p = newRoot;
nodes[a].p = newRoot;
}
int res = nodes[a].val;
nodes[a].val = -1;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
nodes.assign(n + 1, Node());
for (int i = 1; i <= n; i++) {
cin >> nodes[i].val;
nodes[i].p = i;
nodes[i].curQue.insert({ nodes[i].val, i });
}
int op, x, y;
while (m--) {
cin >> op;
if (op == 1) {
cin >> x >> y;
MergeAio(x, y);
continue;
}
cin >> x;
cout << Delete(x) << '\n';
}
return 0;
}
```
by lcyxds @ 2024-03-24 03:04:11