题解 | #[JSOI2008]最大数MAXNUMBER#

线段树 或 ST 表

法1：线段树

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

int m,d;
struct node{
    int l,r;
    int maxm;
}tr[N*4];

void pushup(int u){
    tr[u].maxm=max(tr[u<<1].maxm,tr[u<<1|1].maxm);
}

void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r) return ;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}

void modify(int u,int pos,int v){
    if(tr[u].l==pos&&tr[u].r==pos) tr[u].maxm=v;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(pos<=mid) modify(u<<1,pos,v);
        else modify(u<<1|1,pos,v);
        pushup(u);
    }
}

int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxm;

    int v=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v=max(v,query(u<<1|1,l,r));

    return v;
}

int main(){
    cin>>m>>d;
    build(1,1,m);

    int n=0,t=0;
    char op[2]; int x;
    while(m--){
        cin>>op>>x;
        if(op[0]=='A') modify(1,++n,(x+t)%d);
        else {
            t=query(1,n-x+1,n);
            cout<<t<<endl;
        }
    }
    return 0;
}

法2：ST 表

逆求 f[i][j]

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

int lg[N];
int f[N][20];  // f[i][j]：从 i 开始 向左连续 2^j 个数（包括 i ），该区间里的最大值
int m,d;
int n,t;

void Init(){
    lg[1]=0;
    lg[2]=1;
    for(int i=3;i<=N;i++) lg[i]=lg[i/2]+1;
}

void change(int v){
    n++;
    int k=lg[n];
    f[n][0]=v;
    for(int j=1;j<=k;j++) f[n][j]=max(f[n][j-1],f[n-(1<<(j-1))][j-1]);
}

int main(){
    cin>>m>>d;
    Init();

    char op[2];  int x;
    while(m--){
        cin>> op>>x;
        if(op[0]=='A')  change((t+x)%d);
        else {
            int k=lg[x];
            int p=(1<<k)-x+n;
            t=max(f[n][k],f[p][k]);
            cout<<t<<endl;
        }
    }
    return 0;
}