[关闭]
@RabbitHu 2017-08-07T11:31:24.000000Z 字数 1191 阅读 1504

暑假集训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,修改就是直接修改。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 1000005;
  8. int n, cnt;
  9. struct data {
  10. int num, pos; //num:节点存储的“区间最大值”;pos:节点最大值在序列中所在的下标
  11. data() : num(0), pos(0) {}
  12. bool operator < (data b) const{
  13. return num == b.num ? pos > b.pos : num < b.num;
  14. }//如果最大值不相等,比较最大值;相等则比较最大值下标
  15. } dta[2 * N];
  16. void change(int k, int l, int r, int p, int x){
  17. if(l == r) {
  18. dta[k].pos = p, dta[k].num = x;//修改节点最大值为x,下标为p
  19. return;
  20. }
  21. int mid = (l + r) >> 1;
  22. if(p <= mid) change(k << 1, l, mid, p, x); //左儿子
  23. else change(k << 1 | 1, mid + 1, r, p, x); //右儿子
  24. dta[k] = max(dta[k << 1], dta[k << 1 | 1]); //更新
  25. }
  26. int main(){
  27. scanf("%d", &n);
  28. for(int i = 1; i <= n; i++){
  29. int op;
  30. scanf("%d", &op);
  31. if(op == 1){//push操作就是在序列的最后加一个数
  32. int tmp;
  33. scanf("%d", &tmp);
  34. change(1, 1, n, ++cnt, tmp);
  35. }
  36. else if(op == 2){//pop操作就是把最大的那个数改成0
  37. change(1, 1, n, dta[1].pos, 0);
  38. }
  39. else{//修改操作就是直接修改
  40. int p, x;
  41. scanf("%d%d", &p, &x);
  42. if(p <= cnt)
  43. change(1, 1, n, p, x);
  44. }
  45. printf("%d\n", dta[1].num ? dta[1].num : -1);
  46. }
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注