暑假集训D4T6

题解

链接：uoj.今晚吃什.么

题面

实现一个优先队列。

【输入格式】

第一行一个整数n，表示操作次数。

接下来n行每行一个操作：

1 x，将一个数x插入优先队列（1≤x≤10^9）
2，弹出最大的元素（如果已经为空则什么都不做，如果有多个最大的元素，则弹出先插入的）
3 i x，将第i次插入的数修改为x（如果已经出队，则将其重新入队，并且其“插入时间”以之前的计算；如果i越界，则什么都不做，1≤i,x≤10^9）
【输出格式】

每次操作结束后，输出一行一个数，表示当前优先队列中的最大元素。如果为空则输出-1。

题解

可以线段树搞……

优先队列中最多只有n个元素，可以看做一个序列，每次push就是在序列末尾新增一个数，pop就是改成0，修改就是直接修改。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1000005;
int n, cnt;
struct data {
    int num, pos; //num：节点存储的“区间最大值”；pos：节点最大值在序列中所在的下标
    data() : num(0), pos(0) {}
    bool operator < (data b) const{
        return num == b.num ? pos > b.pos : num < b.num;
    }//如果最大值不相等，比较最大值；相等则比较最大值下标
} dta[2 * N];
void change(int k, int l, int r, int p, int x){
    if(l == r) {
        dta[k].pos = p, dta[k].num = x;//修改节点最大值为x，下标为p
        return;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) change(k << 1, l, mid, p, x); //左儿子
    else change(k << 1 | 1, mid + 1, r, p, x); //右儿子
    dta[k] = max(dta[k << 1], dta[k << 1 | 1]); //更新
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        int op;
        scanf("%d", &op);
        if(op == 1){//push操作就是在序列的最后加一个数
            int tmp;
            scanf("%d", &tmp);
            change(1, 1, n, ++cnt, tmp);
        }
        else if(op == 2){//pop操作就是把最大的那个数改成0
            change(1, 1, n, dta[1].pos, 0);
        }
        else{//修改操作就是直接修改
            int p, x;
            scanf("%d%d", &p, &x);
            if(p <= cnt)
                change(1, 1, n, p, x);
        }
        printf("%d\n", dta[1].num ? dta[1].num : -1);
    }
    return 0;
}