P1988 最大数

最大数

08年江苏的一道省选题。

题目描述：

用两种操作维护一个数列：

1、查询：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

2、插入：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

这道题的解决方法有不少，例如单调栈，单调队列，线段树之类的。

由于把这道题当作单调栈的练习来做的，所以就只用了单调栈。别的方法可以参考一下黄学长的博客。

思路：

不断的维护一个单调递减的栈，每次输出后面要求输出的第n位就好了。

代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int n,m,b,sum[],dis[],top,x,num;

 char a[];

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i){

         scanf("%s%d",a,&b);

         if(a[]=='A'){

             b=(b+x)%m;

             sum[++num]=b;

             while(top&&sum[dis[top]]<=b)

                 top--;

             dis[++top]=num;

         }

         else{

             int y=lower_bound(dis+,dis+top+,num-b+)-dis;

             x=sum[dis[y]];

             printf("%d\n",x);

         }

     }

     return ;

 }

巴特西

P1988 最大数

最大数

最新文章

热门文章