维护一段区间的最大值 注意为0的区间长度
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define ll long long #define rg register #define lson o<<1 #define rson o<<1|1 const int N=200000+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827; int q,cnt=0; ll mod,t=0,mx[N<<2]; char op; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } void pushup(int o){ mx[o]=max(mx[lson],mx[rson]); } void add(int p,ll k,int o,int l,int r){ if(l==r) {mx[o]=k;return;} int mid=(l+r)>>1; if(mid>=p) add(p,k,lson,l,mid); if(mid<p) add(p,k,rson,mid+1,r); pushup(o); } ll query(int o,int l,int r,int x,int y){ if(r<x||y<l) return -inf; if(x<=l&&r<=y) return mx[o]; int mid=(l+r)>>1; ll a=-inf,b=-inf; a=query(lson,l,mid,x,y); b=query(rson,mid+1,r,x,y); return max(a,b); } int main(){ rd(q),rd(mod); for(int i=1;i<=q;++i){ ll x; cin>>op;rd(x); if(op=='A') add(++cnt,(x+t)%mod,1,1,q); else{ if(!x) t=0; else t=query(1,1,q,cnt-x+1,cnt); printf("%lld ",t); } } return 0; }