思路

此题需要实现单点修改和区间查询，线段树和树状数组都可以用

树状数组 $O(nlogn)$

参考文献

https://www.acwing.com/solution/content/106112/

C++ 代码

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

const int N = 2e5+5;

int m, p, a, len, t;

int tr[N];

int lowbit(int x){
    return x & -x;
}

void update(int x, int k){
    for(int i = x; i <= m; i += lowbit(i)){
        tr[i] = max(tr[i], k);
    }
}

int ask(int x){
    int res = 0;
    for(int i = x;i;i -= lowbit(i)){
        res = max(res, tr[i]);
    }
    return res;
}

int main() {
//  ios::sync_with_stdio(0);
//  cin.ite(0);cout.tie(0);

    scanf("%d%d",&m,&p);

    char op[2];
    int j = m;
    for(int i = 0;i<m;i++){
        scanf("%s %d", op, &t);
        if(op[0]=='Q'){ 
            a = ask(j+t);
            printf("%d\n",a);
        }
        else{   
            update(j--, ((long long)t + a)%p);
        }
    }
    return 0;
}

线段树 $O(nlogn)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc p<<1|1

const int N = 2e5+5;

int m, p, a, len, t;

struct node{
    int l,r,val;
//  int add;
}tr[N*4];

void pushup(int p){
    tr[p].val = max(tr[lc].val, tr[rc].val);
}

//void pushdown(int p){ 
//}

void build(int p, int l, int r){
    tr[p] = {l,r,0};
    if(l == r)return;
    int m = l+r>>1;
    build(lc,l,m);
    build(rc,m+1,r);
//  pushup(p);
}

void update(int p, int x, int k){
    if(tr[p].l == tr[p].r){
        tr[p].val += k;
        return; 
    }
    int m = tr[p].l + tr[p].r >> 1;
    if(x<=m) update(lc, x, k);
    else update(rc, x, k);
    pushup(p); 
}

int ask(int p, int x, int y){
    if(tr[p].l>=x && tr[p].r<=y)return tr[p].val;
    int m = tr[p].l + tr[p].r >> 1;
    int res = 0;
    if(x<=m) res = max(res, ask(lc, x, y));
    if(y>m) res = max(res, ask(rc, x, y));
    return res;
}

int main() {
//  ios::sync_with_stdio(0);
//  cin.ite(0);cout.tie(0);

    scanf("%d%d",&m,&p);

    build(1, 1, m);

    char op[2];
    while(m--){
        scanf("%s",op);
        if(op[0]=='Q'){
            scanf("%d",&t);
            a = ask(1, len-t+1,len);
            printf("%d\n",a);
        }
        else{
            scanf("%d",&t);
            update(1, ++len, ((long long)t + a)%p);
        }
    }
    return 0;
}