学步园

单调队列的入门题型。学习斜率优化DP的一个铺垫。

需要注意的一点是：虽然单次操作的复杂度可能不是O(1)，但是单调队列中的每个元素都只入队和出队了一次，这样平摊下来，单次操作的复杂度仍然是O(1)。

#include<stdio.h>
#include<string.h>
#define N 1000005
int a[N],mark[N];
int main()
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        char s[15];
        scanf("%s",s);
        getchar();
        int cnt,head,tail;
        head=tail=0;
        cnt=0;
        int i;
        i=1;
        while(scanf("%s",s),strcmp(s,"END")!=0)
        {
            if(s[0]=='C')
            {
                scanf("%s%d",s,&a[i]);
                while(head<tail&&a[i]>a[mark[tail-1]])
                    tail--;
                mark[tail++]=i;
                i++;
            }
            else if(s[0]=='G')
            {
                cnt++;
                if(cnt==mark[head]&&head!=tail)
                    head++;
            }
            else if(s[0]=='Q')
            {
                if(head==tail)
                {
                    printf("-1\n");
                }
                else
                    printf("%d\n",a[mark[head]]);
            }
            getchar();
        }
    }
    return 0;
}