可查询双端队列

Minclxc · 2018-09-29 23:18:53 · 题解

我们需要维护一个可以查询最大值的双端队列
支持五种操作：头部插入、尾部插入、头部弹出、尾部弹出、查询最大值

双端队列其实和栈的性质更为相似
所以从中点维护两个向左、向右的单调栈可以实现
如果左、右端点超过中点，则重新标记中点，重构单调栈

下面证明重构操作是O(1)的
要重构单调栈操作为O(n)需要不平衡度(即左右个数差)为n
重构后不平衡度变成0(或1)
而不平衡度是插入或删除操作积累的，而每个操作最多+1
所以将重构的复杂度均摊进插入删除操作中，复杂度为O(1)
实际上插入删除也可能导致不平衡度减少，所以重构的复杂度其实较低

以下为代码

#include<cstdio>
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
#define go(a,b,c) for(int a=b;a>=c;a--)
#define max(a,b) ((a)>(b)?(a):(b))
int read(){
    int a=0,f=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
    return f?-a:a;
}
const int N=2e7+1;
int qu[N],pst[N],qst[N],pt,qt,s=1e7+1,t=1e7,mid=t;
void pushp(int x){
    if(!pt||qu[pst[pt]]<qu[x])pst[++pt]=x;
}
void pushq(int x){
    if(!qt||qu[qst[qt]]<qu[x])qst[++qt]=x; 
}
void rebuild(){
    mid=s+t>>1;pt=qt=0;
    go(i,mid,s)pushp(i);
    fo(i,mid+1,t)pushq(i);
}
int main(){
    int n=read();
    fo(i,1,n){
        int opt=read();
        if(opt==1){qu[--s]=read();pushp(s);}//头部插入
        if(opt==2){qu[++t]=read();pushq(t);}//尾部插入
        if(opt==3){
            if(pt&&pst[pt]==s)pt--;
            if(qt&&qst[qt]==s)qt--;
            if(++s>mid)rebuild();
        }//头部弹出
        if(opt==4){
            if(pt&&pst[pt]==t)pt--;
            if(qt&&qst[qt]==t)qt--;
            if(--t<=mid)rebuild();
        }//尾部弹出
        if(opt==5)printf("%d\n",max(qu[pst[pt]],qu[qst[qt]]));//查询最大值
    }
    return 0;
}