题解 P1198 【[JSOI2008]最大数】

Xyasummer · 2016-11-16 00:02:37 · 题解

给一个比较简单的做法，由于先入队的较小数，在有后入队的大数的情况下不可能为答案，所以，可以维护一个单调队列。由于单调队列中入队先后，与数的大小皆是有序的，故可以用二分查找找到单调队列中，在后l个数里，最靠近队首(最大)的数，即为答案。

ps：（1）线段树常数大故此做法要快得多 （2）c++中可用函数lower_bound实现二分查找功能。

代码如下。

#include<cstdio>  
#include<cstring>
#include<algorithm>
using namespace std;
int f[200010],a[200010];
int main(){
    int t=0,j=0,m,d,x,i,k,l=0;
    char ch[2];
    scanf("%d%d",&m,&d);
    for(i=1;i<=m;i++)
    {
        scanf("%s%d",ch,&x);
        if (ch[0]=='A')
        {
            k=(x+t)%d;
            while(j>0 && f[j]<k)j--;j++;
            f[j]=k;
            l++;a[j]=l;
        }
        else 
           printf("%d\n",t=f[lower_bound(a+1,a+j+1,l-x+1)-a]);
    }
    return 0;
}