bzoj 1012--最大數maxnumber 線段樹

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn=200000+1000;
const ll INF=-1e18;

ll node[maxn<<2];
ll Mod;
int tot;

void build(int l,int r,int root){
  
  node[root]=INF;
  if(l==r) return ;
  int mid=(l+r)>>1;
  build(l,mid,root<<1);
  build(mid+1,r,root<<1|1);
}
void Update(int l,int r,int ind,int root,ll val){
  
  if(l==r) {
    
    node[root]=val;
    return ;
  }
  int mid=(l+r)>>1;
  if(mid>=ind) Update(l,mid,ind,root<<1,val);
  else Update(mid+1,r,ind,root<<1|1,val); 
  node[root]=max(node[root<<1],node[root<<1|1]);
}

ll query(int l,int r,int L,int R,int root){
  
  if(l<=L&&r>=R) return node[root];
  int mid=(L+R)>>1;
  if(mid<l) return query(l,r,mid+1,R,root<<1|1);
  else if(mid>=r) return query(l,r,L,mid,root<<1);
  else return max(query(l,r,L,mid,root<<1),query(l,r,mid+1,R,root<<1|1));
}

int main(){
  
  int n;
  scanf("%d%lld",&n,&Mod);
  ll t=0;
  build(1,n,1);
  for(int i=0;i<n;i++){
    
    char tmp[10];
    ll x;
    scanf("%s%lld",tmp,&x);
    if(tmp[0]=='A'){
      
      x=(x+t)%Mod;
      tot++;
      Update(1,n,tot,1,x);
    }
    else{
      
      printf("%lld\n",t=query(tot-x+1,tot,1,n,1));
    }
  }
}