luogu_1198 ?[JSOI2008]最大数

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring> ???using namespace std;long long n,mod,a[2000010],t,cnt,y;int Max(int a,int b){ ???if(a>=b)return a; ???else return b;}inline void update(int l,int r,int now,int v,int o){ ???if(l==now && r==now){a[o]=v; return;} ???if(l==r)return; ???int mid=(l+r)>>1; ???if(mid>=now)update(l,mid,now,v,o<<1); ???else update(mid+1,r,now,v,o<<1|1); ???a[o]=Max(a[o<<1],a[o<<1|1]);}inline int query(int l,int r,int L,int R,int o){ ???if(l>R || r<L)return -1; ???if(L<=l && r<=R)return a[o]; ???int mid=(l+r)>>1; ???int q1=query(l,mid,L,R,o<<1); ???int q2=query(mid+1,r,L,R,o<<1|1); ???if(q1==-1)return q2; ???if(q2==-1)return q1; ???return Max(q1,q2);}int main(){ ???long long k=0; ???scanf("%lld%lld",&n,&mod); ???while((1<<k)<n)k++; ???k=1<<k; ???while(n--){ ???????char x; ???????x=getchar(); ???????while(x!=‘A‘ && x!=‘Q‘)x=getchar(); ???????if(x==‘A‘){ ???????????scanf("%lld",&y); y=(y+t)%mod; ???????????cnt++; ???????????update(1,k,cnt,y,1); ???????} ???????else if(x==‘Q‘){ ???????????scanf("%lld",&y); ???????????t=query(1,k,cnt-y+1,cnt,1); ???????????printf("%lld\n",t); ???????} ???} ???return 0;}