最大数（cogs 1844）

【题目描述】

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

【输入格式】

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足

【输出格式】

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

【样例输入】

【样例输出】

96
93
96

/*
  线段树维护最大值
  注意这里的n可以为查询次数，因为n最大为查询次数 
*/
#include<cstdio>
#include<iostream>
#define M 200010
#define lson l,m,now*2
#define rson m+1,r,now*2+1
#define LL long long
using namespace std;
LL mx[M*4],mod,t=0,n;
LL read()
{
    char c=getchar();LL num=0,flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return num*flag;
}
void push_up(int now)
{
    mx[now]=max(mx[now*2],mx[now*2+1]);
}
void insert(LL v,LL pos,LL l,LL r,LL now)
{
    if(l==r)
    {
        mx[now]=v;
        return;
    }
    LL m=(l+r)/2;
    if(pos<=m)insert(v,pos,lson);
    else insert(v,pos,rson);
    push_up(now);
}
LL query(LL x,LL y,LL l,LL r,LL now)
{
    if(l>=x&&r<=y)return mx[now];
    LL m=(l+r)/2;
    LL ans=0;
    if(m>=x)ans=max(ans,query(x,y,lson));
    if(m<y)ans=max(ans,query(x,y,rson));
    return ans;
}
int main()
{
    freopen("bzoj_1012.in","r",stdin);
    freopen("bzoj_1012.out","w",stdout);
    LL T=read(),p=0;mod=read();n=T;
    while(T--)
    {
        char c;cin>>c;
        LL x=read();
        if(c=='Q')
        {
            LL ans=query(p-x+1,p,1,n,1);
            cout<<ans<<endl;
            t=ans;
        }
        else
        {
            p++;
            insert((x+t)%mod,p,1,n,1);
        }
    }
    return 0;
}

View Code