记录编号	454603	评测结果	WWWWWWWWWW
题目名称	[JSOI 2008] 最大数	最终得分	0
用户昵称	FFF团	是否通过	未通过
代码语言	C++	运行时间	0.494 s
提交时间	2017-09-29 10:01:41	内存使用	11.76 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000000;
const int INF=0x7fffffff;
struct segmenttree{
    int a[maxn],maxv[2*maxn];
    void bulid(int o,int l,int r){
        if(l==r){
            maxv[o]=a[l];
            return ;
        }int m=l+(r-l)/2,lo=2*o,ro=2*o+1;
        bulid(lo,l,m);
        bulid(ro,m+1,r);
        maxv[o]=max(maxv[lo],maxv[ro]);
    }
    int query_max(int o,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr)return maxv[o];
        int m=l+(r-l)/2,lo=2*o,ro=2*o+1,res=-INF;
        if(ql<=m)res=max(res,query_max(lo,l,m,ql,qr));
        if(qr>m)res=max(res,query_max(ro,m+1,r,ql,qr));
        return res;
    }
    void add(int o,int l,int r,int pos,int num){
        if(l==r){
            a[pos]+=num,maxv[o]+=num;
            return ;
        }
        int m=l+(r-l)/2,lo=2*o,ro=2*o+1;
        if(pos<=m)add(lo,l,m,pos,num);
        if(pos>m)add(ro,m+1,r,pos,num);
        maxv[o]=max(maxv[lo],maxv[ro]);
        return ;
    }
};
segmenttree tree;
int m,d,t,n,cnt,l;
char c;
int main(){
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
    scanf("%d%d",&m,&d);
    for(int i=1;i<=m;i++)tree.a[i]=0;
    tree.bulid(1,1,m);
    for(int i=1;i<=m;i++){
        scanf("\n%c",&c);
        if(c=='A'){
            scanf("%d",&n);
            n+=t;n%=d;
            tree.add(1,1,m,++cnt,n);
        }
        if(c=='Q'){
            scanf("%d",&l);
            t=tree.query_max(1,1,m,cnt-l+1,cnt);
            printf("%d\n",t);
        }
    }
    return 0;
}