LOJ #10127. 「一本通 4.3 练习 1」最大数 题解
题目链接:LOJ
咕咕咕
#include
#include
#include
#define ls p<<1
#define int long long
#define rs p<<1|1
using namespace std;
int n,m,a[4000005],maxdat[4000005],lazy[4000005];
int last,p;
int tot;
int q;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
inline void down(int p,int l,int r){
int mid=l+r>>1;
lazy[ls]+=lazy[p];
lazy[rs]+=lazy[p];
maxdat[ls]+=lazy[p];
maxdat[rs]+=lazy[p];
lazy[p]=0;
}
inline void update(int p,int x,int y,int l,int r,int k){
if(x<=l&&y>=r){
maxdat[p]+=k;
lazy[p]+=k;
return;
}
down(p,l,r);
int mid=l+r>>1;
if(x<=mid) update(ls,x,y,l,mid,k);
if(y>mid) update(rs,x,y,mid+1,r,k);
maxdat[p]=max(maxdat[ls],maxdat[rs]);
}
inline int query(int p,int x,int y,int l,int r){
if(x<=l&&y>=r) return maxdat[p];
int mid=l+r>>1;
int res=-(1<<30);
if(x<=mid) res=max(res,query(ls,x,y,l,mid));
if(y>mid) res=max(res,query(rs,x,y,mid+1,r));
return res;
}
signed main(){
m=read();p=read();
tot=0;
for(int i=1;i<=m;i++){
char c;
int q,t;
cin>>c;
if(c=='A'){
t=read();
++tot;
int kkk=(t+last)%p;
update(1,tot,tot,1,m,kkk);
}
else{
q=read();
last=query(1,tot-q+1,tot,1,m);
cout<