这道题相对简单下面是题目：

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB

Submit: 6542 Solved: 2795

[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

Sample Output

96

93

96

这个题维护一个区间最值得线段树，根据M的最大值可以先建一个M大的空树，然后开一个变量place记录需要更新哪一个点，并更新即可，点修改+区间查询 愉快的AC（话说bzoj上好久没有一遍A了）.....

下面是代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 200001

int maxnumber[maxn<<2]={0};

void updata(int now)

{

    maxnumber[now]=max(maxnumber[now<<1],maxnumber[now<<1|1]);

}

void build(int l,int r,int now)

{

    maxnumber[now]=0;

    if (l==r) return;

    int mid=(l+r)>>1;

    build(l,mid,now<<1);

    build(mid+1,r,now<<1|1);

    updata(now);

}

void point_change(int l,int r,int now,int loc,int data)

{

    if (l==r)

        {

            maxnumber[now]=data;

            return;

        }

    int mid=(l+r)>>1;

    if (loc<=mid)

        point_change(l,mid,now<<1,loc,data);

    else

        point_change(mid+1,r,now<<1|1,loc,data);

    updata(now);

}

int query(int L,int R,int l,int r,int now)

{

    if (L<=l && R>=r)

        return maxnumber[now];

    int mid=(l+r)>>1;

    int maxans=0;

    if (L<=mid)

        maxans=max(maxans,query(L,R,l,mid,now<<1));

    if (R>mid)

        maxans=max(maxans,query(L,R,mid+1,r,now<<1|1));

    return maxans;

}

int main()

{

    int m,d;

    int place=1;

    int t=0;

    scanf("%d%d",&m,&d);

    build(1,maxn,1);

    for (int i=1; i<=m; i++)

        {

            char command[2];

            scanf("%s",&command);

            if (command[0]=='A')

                {

                    int data;

                    scanf("%d",&data);

                    data=(data+t) % d;

                    point_change(1,maxn,1,place,data);

                    place++;

                }

            else

                {

                    int sum;

                    scanf("%d",&sum);

                    int ans=query(place-sum,place-1,1,maxn,1);

                    printf("%d\n",ans);

                    t=ans;

                }

        }

    return 0;

}