题解 P1198 【[JSOI2008]最大数】

· · 题解

这题用线段树也能AC，但是用线段树做这题似乎有点杀鸡用牛刀的感觉——因为询问的是末尾L个数中的最大数。

由于L不固定，所以用单调栈而不是单调队列。

于是需要维护一个单调递减栈。插入操作和单调队列一样，当当前数大于栈顶时栈顶出栈，然后当前数进栈。由于栈底不能像队首一样被弹出（不存在“过期元素”），查询操作不可能做到O(1)了。显然20W的规模不可能用O(n)的算法进行单次操作。考虑到栈中新进的元素的编号必然比老元素的编号大，即单调栈元素的编号也是单调的，所以查询操作可以优化为：二分搜索栈，找到编号符合条件的第一个元素，复杂度为O(logn)，总复杂度[color=red]O(nlogn)[/color]，这样就能AC了。

PS:单调栈不仅代码短，不容易写错，而且速度比线段树快

代码：


#include<cstdio>
int a[200010],b[200010],k,p,n,x,y,d;
char s[3];
int search(int l,int r,int k){
    int m=(l+r)>>1;
    while (l!=r){
        if (b[m]<k) l=m+1;
        if (b[m]==k) return m;
        if (b[m]>k) r=m;
        m=(l+r)>>1;
    }
    return m;
}
int main(){
    scanf("%d%d",&n,&d);
    x=k=0;
    p=0;
    for (int i=1;i<=n;i++){
        scanf("%s%d",s,&y);
        if (s[0]=='A'){
            y=(x+y)%d;
            k++;
            a[k]=y;
            while (p>0 && a[b[p]]<=y) p--;
            p++;
            b[p]=k;
        }
        if (s[0]=='Q'){
            x=a[b[search(1,p,k-y+1)]];
            printf("%d\n",x);
        }
    }
}