BZOJ1012

BZOJ1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB

Description

现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。

Input

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来M行，查询操作或者插入操作。

Output

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

5 100

A 96

Q 1

A 97

Q 1

Q 2

Sample Output

96

93

96

这是一道单调栈的问题，单调栈维护所有数的最大值。

查询操作时只需要二分找答案即可，枚举栈内的数应该也不会超时。

code：

/************************************************************** Problem: 1012 User: yekehe Language: C++ Result: Accepted Time:304 ms Memory:2384 kb ****************************************************************/ #include <cstdio> using namespace std; inline int read(){ char c;while(c=getchar(),(c<'0'||c>'9')&&c!='-');int x=0,y=1;c=='-'?y=-1:x=c-'0'; while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';return x*y; } int m,d,stuck[200001][2],top,t,now; char c; int so(int l,int r,int x){ int mid; while(l<r){ mid=(l+r)>>1; if(stuck[mid][1]<=x)l=mid+1; else r=mid; } return l; } int main(){ m=read(),d=read();stuck[0][0]=2e9; for(int i=1;i<=m;i++){ c=getchar(); if(c=='A'){ int x=read();x=(x+t)%d; while(stuck[top][0]<x) top--; stuck[++top][0]=x; stuck[top][1]=++now; } else { int w=top,v=read(); w=so(1,top,now-v); printf("%d\n",stuck[w][0]); t=stuck[w][0]; } } return 0; }

O(KM)_k为常数。