Miku

仍然还是线段树的水题

惨痛教训：不要无脑复制板子

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define int long long 
using namespace std;
long long tree[1000110],ma[1000101];
void pushup(int x){
    ma[x]=max(ma[x<<1],ma[x<<1|1]);
    return ;
}
int t;
void up(int x,int l,int r,int L,int R,int d){
    if(L<=l&&r<=R){
        ma[x]=d;
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) up(x<<1,l,mid,L,R,d);
    if(R>mid) up(x<<1|1,mid+1,r,L,R,d);
    pushup(x);
    return ;
}
int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return ma[x];
    }
    int mid=(l+r)>>1,ans=0;
    int a=-0x7fffff;
    int b=-0x7fffff;
    if(L<=mid) a=query(x<<1,l,mid,L,R);
    if(R>mid) b=query(x<<1|1,mid+1,r,L,R);
    return max(a,b);
}
int m,d;
char c;
int l;
int len=300000;
int x; 
signed main(){
    scanf("%lld%lld",&m,&d);
    for(int i=1;i<=m;++i){
        cin>>c;
        if(c=='A'){
            scanf("%lld",&x);
         l++;
         up(1,1,len,l,l,((x%d+t%d)%d+d)%d);
        }else{
            scanf("%lld",&x);
            t=query(1,1,len,l-x+1,l);
            cout<<t<<endl;
        }
    }
    return 0;
}