最大数（cogs 1844）

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

【样例输出】

/*

  线段树维护最大值

  注意这里的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*],mod,t=,n;

LL read()

{

    char c=getchar();LL num=,flag=;

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return num*flag;

}

void push_up(int now)

{

    mx[now]=max(mx[now*],mx[now*+]);

}

void insert(LL v,LL pos,LL l,LL r,LL now)

{

    if(l==r)

    {

        mx[now]=v;

        return;

    }

    LL m=(l+r)/;

    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)/;

    LL ans=;

    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=;mod=read();n=T;

    while(T--)

    {

        char c;cin>>c;

        LL x=read();

        if(c=='Q')

        {

            LL ans=query(p-x+,p,,n,);

            cout<<ans<<endl;

            t=ans;

        }

        else

        {

            p++;

            insert((x+t)%mod,p,,n,);

        }

    }

    return ;

}

巴特西