How to AK ABC253

__vector__ · 2022-05-30 21:20:43 · 个人记录

题外话：

E 题过样例，然而没调出来。
最后 rating: \color{brown}\text{725} \rightarrow \color{brown}\text{747}

A

略

B

略

C

题目翻译：

给你一个空集合 S
有 Q 次操作，每次操作分三种类型。

1. 给定 x，向 S 中加入 x
2. 给定 x 和 c，设 m 等于 c 与 (x 在 S 中出现的次数) 的 min。重复从 S 中删除 x 数 m 次
3. 输出集合中最大的数与集合中最小的数的差，保证进行此操作时集合不为空。

数据范围：

做法：

我说一下我的做法和 \color{black}\text{t}\color{red}\text{ourist} 的做法

我的做法：
可以使用一个大根堆和一个小根堆（就是两个 priority_queue）来维护最大值和最小值。然后使用 map 记录每个数出现的次数。
当加入一个数时，就将其同时丢进大根堆和小根堆，然后 map 记录这个数出现的次数加一
删数的时候，直接将 map 记录的这个数出现的次数减一就行了。要注意的是，删数的过程可能会把最大值或最小值删没，这样会影响到操作三查询结果，所以在操作三查询的时候要将大根堆和小根堆的 (通过 map 记录的 (出为 0 的队首元素)) 通过 while 不断弹出，直到队首元素在 map 中的记录次数不为 0。
至于中间的非最大最小值的数不用管，因为查询用不着，不用将它们弹出。
复杂度： O(nlogn)
我的代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    int q;
    int op,x,c;
    priority_queue<int> que;
    priority_queue<int> que2;
    unordered_map<int,int> im;

    void main()
    {
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d",&x);
                if(!im[x])
                {
                    que.push(x);
                    que2.push(-x);
                }
                im[x]++;
            }
            if(op==2)
            {
                scanf("%d%d",&x,&c);
                int m=min(c,im[x]);
                im[x]-=m;
            }
            if(op==3)
            {
                while(im[que.top()]==0)
                {
                    que.pop();
                }
                while(im[-que2.top()]==0)
                {
                    que2.pop();
                }
                int imax=que.top();
                int imin=-que2.top();
                printf("%d\n",imax-imin);
            }
        }
    }
}
int main()
{
    Main::main();
    return 0;
}