记录编号	398332	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.513 s
提交时间	2017-04-21 22:40:59	内存使用	13.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int m,l;
int jl[200001],dq=1;
char cz;
long long d,n,t;
struct mn
{
  int l,r;
  long long mx;
  mn(){l=0;r=0;mx=0;}
}tree[800001];
void build(int l,int r,int now)
{
  int mid=(l+r)/2;
  tree[now].l=l;
  tree[now].r=r;
  if(l==r)
  {
    jl[l]=now;
    return;
  }
  build(l,mid,2*now);
  build(mid+1,r,2*now+1);
}
void gx(int now)
{
  while(now)
  {
    tree[now].mx=max(tree[2*now].mx,tree[2*now+1].mx);
    now/=2;
  }
}
void s(int dl,int dr,int now)
{
  int mid=(tree[now].l+tree[now].r)/2;
  if(dl==tree[now].l&&dr==tree[now].r)
  {
    t=max(tree[now].mx,t);
    return;
  }
  if(dr<=mid)
  {
    s(dl,dr,2*now);
    return;
  }
  if(dl>mid)
  {
    s(dl,dr,2*now+1);
    return;
  }
  s(dl,mid,2*now);
  s(mid+1,dr,2*now+1);
}
int main()
{
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
  scanf("%d%lld",&m,&d);
  build(1,200000,1);
  for(int i=1;i<=m;i++)
  {
    scanf("%s",&cz);
    if(cz=='A')
    {
      scanf("%lld",&n);
      n+=t;
      n%=d;
      tree[jl[dq]].mx=n;
      gx(jl[dq]/2);
      dq++;
    }
    else
    {
      scanf("%d",&l);
      t=0;
      s(dq-l,dq-1,1);
      printf("%lld\n",t);
    }
  }
  return 0;
}