洛谷

https://www.luogu.org/problemnew/show/P1198

要问区间最大值，肯定是要用线段树的，不能用树状数组。（因为没有逆元？但是题目求的是最后一段，可以改成类似前缀和啊。不行！插入新元素之后更新的复杂度太高了！）

所以我们就弄一个初始元素是负数的最大值线段树，每次插入就是把末尾的元素 $update$ ，查询就是查询末尾的区间最大值，这样每次修改/查询的复杂度是 $O(nlogn)$ 的，非常给力。

所以说我又要到哪里抄一个线段树模板。

注意这个线段树是从1开始计数的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int MAXM=200000;
int a[MAXM+5],st[(MAXM<<2)+5];

void build(int o,int l,int r){
    if(l==r) st[o]=a[l];
    else{
        int m=l+((r-l)>>1);
        build(o<<1,l,m);
        build(o<<1|1,m+1,r);
        st[o]=max(st[o<<1],st[o<<1|1]);
    }
}

void update(int o,int l,int r,int id,int v){
    if(l==r) st[o]=v;
    else{
        int m=l+((r-l)>>1);
        if(id<=m) update(o<<1,l,m,id,v);
        else update(o<<1|1,m+1,r,id,v);
        st[o]=max(st[o<<1],st[o<<1|1]);
    }
}

int query(int o,int l,int r,int a,int b){
    if(r<a||l>b) return -1;
    if(a<=l&&r<=b) return st[o];
    int m=l+((r-l)>>1);
    int p1=query(o<<1,l,m,a,b),p2=query(o<<1|1,m+1,r,a,b);
    return max(p1,p2);
}


int M;
ll D;
int t;

char s[5];
int ins;

int cntA=0;

int main(){
    t=0;
    scanf("%d%lld",&M,&D);
    for(int i=1;i<=M;i++){
        a[i]=-1;
    }
    build(1,1,M);
    for(int i=1;i<=M;i++){
        scanf("%s%d",s,&ins);
        if(s[0]=='Q'){
            t=query(1,1,M,cntA-ins+1,cntA);
            printf("%d
",t);
        }
        else{
            update(1,1,M,cntA+1,((1ll*ins)+t)%D);
            cntA++;
        }
    }
}