# 11050: 【原1050】二哥的优先队列

### 题目描述

author: ghostgold 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1050

## Description

1. 将一组并入另一组
2. 将一组中魅力值最小的拿走
3. 给某一组中添加一个女生

## Sample Input

5 9
0
36
49
98
3
1 4
0 2 4
1 1
0 0 3
1 0
0 1 2
0 0 1
2 0 15
1 0


## Sample Output

3
36
0
15


## FineArtz's solution

/* 二哥的优先队列 */
#include <iostream>
using namespace std;

class Node{
public:
int data = 0, dist = -1;
Node *l = nullptr, *r = nullptr;
};

Node* a[300005];
bool b[300005];
int n, m;

template<class T>
inline void swp(T &x, T &y){
T t = x; x = y; y = t;
}

Node *merge(Node *x, Node *y){
if (x == nullptr) return y;
if (y == nullptr) return x;
if (x->data > y->data)
swp(x, y);
x->r = merge(x->r, y);
if (x->l == nullptr || x->l->dist < x->r->dist)
swp(x->l, x->r);
if (x->r == nullptr)
x->dist = 0;
else
x->dist = x->r->dist + 1;
return x;
}

void dispose(Node *x){
if (x == nullptr)
return;
if (x->l != nullptr)
dispose(x->l);
if (x->r != nullptr)
dispose(x->r);
delete x;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
Node *t = new Node;
cin >> t->data;
t->dist = 0;
a[i] = t;
b[i] = true;
}
while (m--){
int imp, x, y;
cin >> imp;
switch (imp){
case 0:
cin >> x >> y;
++x; ++y;
a[x] = merge(a[x], a[y]);
b[y] = false;
break;
case 1:
cin >> x;
++x;
if (!b[x] || a[x] == nullptr) cout << "-1" << '\n';
else{
cout << a[x]->data << '\n';
Node *t = a[x];
a[x] = merge(a[x]->l, a[x]->r);
delete t;
}
break;
case 2:{
cin >> x >> y;
++x;
Node *t = new Node;
t->data = y;
t->dist = 0;
a[x] = merge(a[x], t);
break;
}
default:
break;
}
}
for (int i = 1; i <= n; ++i){
if (b[i])
dispose(a[i]);
}
return 0;
}


## q4x3's solution

/**
* 左堆
* aaaaaaaaaawsl
* 根节点较大的堆与另一个堆的右子树归并
* 若产生的堆违反左堆定义，交换左右子树
* 某个堆为空时，另一个堆就是归并结果
**/
#include <iostream>

using namespace std;

struct node {
int dt, npl;
node *l, *r;
node():dt(0), npl(-1), l(nullptr), r(nullptr) {}
};

int siz[300233];
node* n[300233];
int M, N, tmp;

node* merge(node *a, node *b) {
if(! a) return b;
if(! b) return a;
if(a->dt > b->dt) swap(a, b);
a->r = merge(a->r, b);
if((! a->l) || (a->l->npl < a->r->npl)) swap(a->l, a->r);
if(! a->r) a->npl = 0;
else a->npl = a->npl = a->r->npl + 1;
return a;
}

int main() {
scanf("%d%d", &N, &M);
for(int i = 1;i <= N;++ i) {
scanf("%d", &tmp);
n[i] = new node;
n[i]->dt = tmp; n[i]->npl = 0;
siz[i] = 1;
}
for(int i = 1;i <= M;++ i) {
scanf("%d", &tmp);
if(tmp == 0) {
int a, b;
scanf("%d%d", &a, &b);
++ a; ++ b;
siz[a] += siz[b];
siz[b] = 0;
n[a] = merge(n[a], n[b]);
n[b] = nullptr;
} else if(tmp == 1) {
int a;
scanf("%d", &a);
++ a;
if(siz[a] == 0 || ! n[a]) {
printf("-1\n");
continue;
}
else printf("%d\n", n[a]->dt);
n[a] = merge(n[a]->l, n[a]->r);
-- siz[a];
} else {
int a, b;
scanf("%d%d", &a, &b);
++ a;
node *newnode = new node;
newnode->dt = b; newnode->npl = 0;
n[a] = merge(n[a], newnode);
++ siz[a];
}
}
}


## victrid's solution

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

struct node {
node* left;
node* right;
int npl;
int value;
};
void npl(node& ps) {
if (ps.left == nullptr || ps.right == nullptr) {
ps.npl = 0;
return;
} else {
ps.npl = min(ps.left->npl, ps.right->npl) + 1;
return;
}
}
node*& merge(node*& lhs, node*& rhs) {
if (rhs == nullptr)
return lhs;
if (lhs == nullptr) {
lhs = rhs;
rhs = nullptr;
return lhs;
}
if (lhs->value > rhs->value) {
merge(rhs, lhs);
lhs = rhs;
rhs = nullptr;
return lhs;
}
lhs->right = merge(lhs->right, rhs);
if (lhs->left == nullptr || lhs->left->npl <= lhs->right->npl) {
node* tmp  = lhs->left;
lhs->left  = lhs->right;
lhs->right = tmp;
}
npl(*lhs);
rhs = nullptr;
return lhs;
}
node* insert(node*& root, int val) {
node* n = new node{nullptr, nullptr, 0, val};
return merge(root, n);
}
int pop(node*& root) {
//I am blind
if (root == nullptr)
return -1;
int ps      = root->value;
node* roots = root;
root        = merge(root->left, root->right);
delete roots;
return ps;
}
node* ns[300010];
int main() {
int n, m, cha, prc, pra, prb;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &cha);
ns[i] = new node{nullptr, nullptr, 0, cha};
}
for (int i = 0; i < m; i++) {
scanf("%d", &prc);
switch (prc) {
case 0:
scanf("%d %d", &pra, &prb);
merge(ns[pra], ns[prb]);
break;
case 1:
scanf("%d", &pra);
printf("%d\n", pop(ns[pra]));
break;
case 2:
scanf("%d %d", &pra, &prb);
insert(ns[pra], prb);
break;
}
}
return 0;
}


## WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
const int mxn=1000000;
int n,m;
int f[mxn],v[mxn],ch[mxn][2],dis[mxn],root[mxn],opt,x,y;
int merge(int x,int y){
if (x==0||y==0)
return x+y;
if (v[x]>v[y]||(v[x]==v[y]&&x>y))
swap(x,y);
ch[x][1]=merge(ch[x][1],y);
f[ch[x][1]]=x;
if (dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][1],ch[x][0]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&v[i]);
root[i]=i;
}
v[0]=-1;
for(int i=0;i<m;i++){
scanf("%d",&opt);
if (opt==0){
scanf("%d%d",&x,&y);
root[x+1]=merge(root[x+1],root[y+1]);
if (!root[y+1]) root[y+1]=-1;
}
if (opt==1){
scanf("%d",&x);
printf("%d\n",v[root[x+1]]);
if (v[root[x+1]]!=-1) {
v[root[x + 1]] = -1;
if (ch[root[x + 1]][0]||ch[root[x+1]][1])
root[x + 1] = merge(ch[root[x + 1]][0], ch[root[x + 1]][1]);
else root[x+1]=0;
}
}
if (opt==2){
scanf("%d%d",&x,&y);
n++;
root[n]=n;
v[n]=y;
root[x+1]=merge(root[x+1],root[n]);
}
}
}


## yyong119's solution

#include <cstdio>
#include <queue>

using namespace std;

int n, m, op, num1, num2;
priority_queue<int, vector<int>, greater<int> > group[300001];

int main() {

scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &num1);
group[i].push(num1);
}

for (int opnum = 1; opnum <= m; opnum++) {
scanf("%d", &op);
switch (op) {
case 0:
scanf("%d%d", &num1, &num2);
while(group[num2].size()) {
group[num1].push(group[num2].top());
group[num2].pop();
}
break;
case 1:
scanf("%d", &num1);
if (group[num1].empty()) printf("%d\n", -1);
else {
printf("%d\n", group[num1].top());
group[num1].pop();
}
break;
case 2:
scanf("%d%d", &num1, &num2);
group[num1].push(num2);
break;
}
}
return 0;
}