Skip to content

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

题目

题目描述

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

Description

二哥把所有女朋友候选人列了出来,一共有N组,编号为0~N-1。最开始的时候每组只有1个女生,每个女生有一个魅力值。二哥不断进行以下三种操作:

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

值得注意的是,如果X组在操作0中被并入其他组,那么二哥将不会再对X组进行这三种操作。

Input Format

第一行:N M(\(0 \leq N,M \leq 300,000 \) )

分别表示最开始的组数与总的操作的次数

接下来N行

每行一个整数,表示最初0~N-1组中那个女生的魅力值

接下来M行

每行首先是一个整数,表示操作编号,0表示合并,1表示拿走魅力值最小的,2表示添加

对于操作0,跟着两个整数,a b,表示将编号为b的组并入编号为a的组(编号为b的组从此消失了)

对于操作1,跟着一个整数,a,表示讲编号为a的组中魅力值最小的女生拿走

对于操作2,跟着两个整数,a b,表示在编号为a的组中添加一个魅力值为b的女生

Output Format

对于每个操作1,输出一行,包含一个整数,表示被拿走的女生的魅力值(如果二哥妄图从一组已经没有人的组内拿走女生,请输出-1)

Hint

大概用某种可合并优先队列。。。

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