题解 P1198 【[JSOI2008]最大数】

蒟蒻365 · 2019-10-01 00:21:12 · 题解

线段树做法就不讲了...ST表也懒得讲...单调栈什么神仙做法我不会也不讲了...

今天我们要讲的是：

单调队列

注意：此题并不能说其是真正的单调队列，只是思想有些类似

代码：

#include<cstdio>
#include<iostream>
using std::cin;
int m,d,a[200001],t,mx[200001],l=0,p;//a为输入数组，t表示元素个数，l表示上一次询问结果
char q;//mx数组即所谓的“单调队列”，表示以i开始，到最后的最大值
int main(){
    scanf("%d%d", &m, &d);
    while(m--){
        cin>>q; 
        scanf("%d",&p);
        if(q=='A'){
            a[++t]=(l+p)%d;
            for(int i=t;i;i--)
                if(mx[i]<a[t])mx[i]=a[t];//得到一个新的值后，往前覆盖
                else break;
        }
        else printf("%d\n",l=mx[t-p+1]);//查询
    }
    return 0;
}

这个算法理论上是能被卡到O（n^2)的（当给出的序列是单调递增时），但是跑得比我的线段树还快...

单调队列，即通过维护一个队列的单调性来获取信息，一般为固定窗口最大/最小值。出队方式有两种，从前出，此时是当窗口大小大于给定窗口时；从后出，此时是当不满足你维护的单调性时。

这题被覆盖掉就相当于从后出队，没有窗口大小也就没有从前出队的操作；且mx数组一定满足单调递减（自己想想为啥）

完结撒花~~