[文章目录]
Description
现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。时限3s
一开始以为是个水题，智障写了个树状数组，怎么都TLE。
然后就不会了，原因是对单调栈这种数据结构不是很熟悉。虽然，最坏的情况是插入O(1)，查询log(n)但已经不知道好到哪里去了。由于此题后面的数如果比前面的大的话，前面的数就不用考虑了，所以我们可以维护一个单调递减的单调栈，每次查询时二分位置，插入整体消耗O(n)的时间。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m,top,n,cnt,t,mod;
char st[30];
int z[201000],id[201000];
void read(int &re)
{
char ch=getchar();re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
}
int main()
{
read(m);read(mod);
while(m--)
{
scanf("%s",st);
switch(st[0])
{
case 'Q':
{
read(n);n=cnt-n+1;
int l=1,r=top+1,mid;
while(l<r)
{
mid=l+r>>1;
if(id[mid]>=n) r=mid;
else l=mid+1;
}
printf("%d\n",t=z[r]);
break;
}
case 'A':
{
cnt++;
read(n);n=(n+t)%mod;
while(top&&z[top]<n) top--;
z[++top]=n;id[top]=cnt;
break;
}
}
}
return 0;
}