P1198 [JSOI2008] 最大数

liu_zheng · 2025-08-01 21:55:51 · 个人记录

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int m,d;
const int maxn=1e6+10;
const int maxx=25;
int a[maxn];
int f[maxn][maxx];
int lg[maxn];
int cmp=0;
    int ans=0;
int q(int l,int r){
    int j=lg[r-l+1];
    return max(f[l][j],f[r+1-(1<<j)][j]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>d;
//  q();

    while(m--){
        char s;
        cin>>s;
        if(s=='A'){
            cmp++;
            int x;
            cin>>x;
            a[cmp]=(x+ans)%d;
            int j=0;
            while((1<<j)<=cmp){
                int i=cmp-(1<<j)+1;
                if(j==0)f[i][j]=a[cmp];
                else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
                j++;    
            }
        }
        if(s=='Q'){
            int x;
            cin>>x;
            ans=q(cmp-x+1,cmp);
            cout<<ans<<'\n';
        }
    }
    return 0;
}