P9588 队列 题解
-
阅读题面，发现只要保存当前已经取到哪个
1\sim x 序列、剩余未取的序列以及当前序列已经被取走多少个数这三种信息就可以了，这需要两个数组和两个首尾指针。 -
看操作
4 ，要求整个序列的最大值。考虑到q \leq 2 \times 10^5 ，不难想到优先队列。因为弹出操作是从前往后弹，所以在单个序列内，只要最后一个x 没有被弹出，该序列就求最大值而言前后没有变化。 -
但是操作
2 怎么办？优先队列每次只能弹出最大值啊？前后的顺序不是乱掉了吗？ -
很急，但是我想到一个办法。对于在操作
2 中被弹出的x ，你让它先别急，先坐下来喝杯茶。然后再把它关进另一个优先队列里，这个优先队列的名字叫“缓冲区”。 -
没有操作
4 的时候，操作2 正常进行，但是原优先队列不弹出。“缓冲区”接收被清空的序列x 。等到操作4 来了的时候，“缓冲区”就可以发挥它的作用了。 -
在耀眼的灯光下，两个优先队列比翼双飞！它们一起弹弹弹，直到两者的
\text{top} 不再相同或者“缓冲区”被弹空为止。至此，我们就找到了一个高效存储先前信息、并将其与原优先队列中的信息快速匹配的办法。
（由于作者太菜了，所以赛时“发明”了双堆法，厉害吧 qwq）
- 但是，这道题还没有结束。操作
2 和操作3 虽然看起来很像，但如果我们都是暴力做的话，前者最多把队列清空，后者却可能跑遍队列10 万次。因此，我们还需要记录操作1 录入序列的前缀和，并在执行操作3 时二分查找。
代码（附注释）：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read() //快读
{
char ch;
ll x=0,f=1;
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-1;
for(; isdigit(ch);ch=getchar())
x*=10,x+=(ch-'0');
return x*f;
}
int c,Q;
priority_queue < int > q; //原优先队列
priority_queue < int > p; //“缓冲区”
int now=1; //头指针
int tot; //尾指针
int a[200005]; //记录存放序列的x
int b[200005]; //记录当前序列已经被取走多少个数
ll f[200005]; //前缀和统计操作1录入的序列
ll anss; //记录操作2已经弹出的数字个数
int main()
{
c=read();
Q=read();
int x,y;
for(int i=1;i<=Q;i++)
{
x=read();
if(x!=4) y=read(); //操作4不用读y
if(x==1)
{
tot++;
a[tot]=y;
b[tot]=y;
q.push(y); //将新序列加入原优先队列
f[tot]=f[tot-1]+y; //前缀和
}
if(x==2)
{
anss+=y; //记录已经被弹出的数字个数
while(y>0)
if(y>=b[now])
{
y-=b[now]; //虚晃一枪
p.push(a[now]); //将弹出序列存入“缓冲区”
now++; //指针移动
}
else
{
b[now]-=y; //没弹完
break;
}
}
if(x==3)
{
int l=now,r=tot;
int mid;
if(y<=b[now]) //当前序列已经足够弹
{
printf("%d\n",a[now]-b[now]+y);
continue;
}
while(l<=r) //二分查找
{
mid=(l+r)/2;
if(f[mid]-anss>y) r=mid-1;
if(f[mid]-anss<y) l=mid+1;
if(y>f[mid-1]-anss&&y<=f[mid]-anss)
break; //找到查询区间
}
printf("%d\n",y-(f[mid-1]-anss));
}
if(x==4)
{
while((!p.empty())&&(!q.empty())&&p.top()==q.top())
p.pop(),q.pop(); //比翼双飞
printf("%d\n",q.top()); //最后得到的原优先队列的top就是答案
}
}
return 0;
}