Description
买彩票是一件很靠rp的事。现在有N条信息描述了一个投注站买票人的信息。
new a 表示在队尾来了一个rp为a的人。
leave 表示队首的人买完离开，数据保证在次操作之前队列不为空。
query 表示询问当前队列中人品最高的人的rp，数据保证这时队列至少有一个人。
Input
输入数据第一行为一个正整数N (1 <= N <= 1000000)。
接着N行每行表示一条信息。
Output
对于每个询问，输出当前队列中最高的rp值。
Sample Input
5
new 30
new 20
query
leave
query
Sample Output
30
20
Solution
看到这道题，我们可以显而易见的想到优先队列
唉，等等，但是这里要删除一些队列中的元素啊
于是我们可以暴力将每一个元素出队
于是我们需要写一个支持删除元素、查找最值的数据结构（平衡树、主席树）
好吧我们baidu一下
咳咳走错片场了
通过亲切的度娘，我们知道可以加延迟标记来支持（？
优先队列懒惰删除法!
我们将要删除的元素建立一个优先队列
然后每次使用原队列前将队首与删除堆的队首比较，当完全相等时，我们就将两个队列都pop一下，就达到了删除元素的效果，而且不会超时（比隔壁单调队列好打多了）
然后这道题就可以轻松切掉了
帖一发code
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int >q,de;
queue<int> ord;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char opt[20];
scanf("%s",opt);
if(opt[0]=='n')
{
int x;
scanf("%d",&x);
q.push(x);
ord.push(x);
}
if(opt[0]=='q')
{
while(!de.empty()&&q.top()==de.top())q.pop(),de.pop();
printf("%d\n",q.top());
}
if(opt[0]=='l')
{
de.push(ord.front());
ord.pop();
}
}
}
飛べる魚 