1012: [JSOI2008]最大数maxnumber
Time Limit: 3 Sec Memory Limit:
162 MB
Submit: 2286 Solved: 1041
[Submit][Status][Discuss]
Description
现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。
Input
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0
Output
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
评测链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1012
解法1:线段树：http://blog.csdn.net/yuyanggo/article/details/8841109
解法2：单调队列+并查集：http://blog.csdn.net/yuyanggo/article/details/8844625
解法3：单调队列+二分查找（即本篇所讲）；
用a[i]记录第i号点的值，用一个单调递减序列q[]（我是从左到右递减）存储从1到n号点所有大于等于a[n]的节点的编号。
对于一个插入操作，假如是插入x，用二分查找找到从左到右第一个<=x的节点的编号j，将q[j]赋值为x的节点编号，并把j后面的元素都删掉（可以用len记录q数组元素总数，把len赋值为j就可以完成这个操作了）
对于一个查询操作Q L，用二分查找找到从左到右第一个>=n-l+1(n为当前节点总数)的点j，然后输出a[q[j]]即可。
（有疑问的欢迎留言）
代码：
#include<cstdio>
#define maxn (200000+100)
using namespace std;
//q记录单调递减队列 a记录节点值
// n记录节点总数 len记录单调队列中的元素总数
int q[maxn],a[maxn],n=0,len=0;
void init()
{
freopen("maxnumber.in","r",stdin);
freopen("maxnumber.out","w",stdout);
}
//将a[k]=x插入单调队列
inline void add(int x,int k)
{
if(x<a[q[len]]){q[++len]=k;return;}
int l=1,r=len,m;
while(l<=r)
{
m=(l+r)>>1;
if(x==a[q[m]]){len=m;return;}
if(x>a[q[m]])r=m-1;
else l=m+1;
}
//找到从左到右第一个<=x的节点的编号L，将q[L]赋值为k（x的节点编号），并将len赋为L，
len=l;q[len]=k;
}
inline int get(int k)
{
if(len==1)return a[n];
int l=1,r=len,m;
while(l<=r)
{
m=(l+r)>>1;
if(q[m]==k)return a[k];
if(k>q[m])l=m+1;
else r=m-1;
}
//找到从左往右第一个节点编号>=k的点L，a[q[l]]即为从k到n的最大值
return a[q[l]];
}
void work()
{
int m,d,t=0,i,b,k;
char s;
scanf("%d%d\n",&m,&d);
for(i=1;i<=m;i++)
{
scanf("%c%d\n",&s,&b);
if(s=='A')
{
a[++n]=(b+t)%d;
add(a[n],n);
}
else
printf("%d\n",t=get(n-b+1));
}
}
int main()
{
init();
work();
return 0;
}