线段树

#define lc k << 1        // 左孩子存储下标 2k, 从 1开始存储
#define rc k << 1 | 1    // 右孩子下标 2k+1
int n;
int a[N];

// 携带区间信息的线段树
struct Node {
  int l, r;
  int max_;    // max_为区间 [l, r]的最大值
}tree[N * 4];

// 递归创建线段树, k表示存储下标, 区间为 [l ,r]
void build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;

  // 叶子结点
  if(l == r) {
    tree[k].max_ = a[l];
    return;
  }

  int mid = l + r >> 1;
  build(lc, l, mid);
  build(rc, mid + 1, r);

  tree[k].max_ = max(tree[lc].max_, tree[rc].max_);
}

// 点更新, 从 tree[0]开始在其左右子树中找叶子结点 a[i], 将 a[i]修改为 v
void update(int k, int i, int v) {
  // 到达目标叶子结点(可能到达别的叶子结点)
  if(tree[k].l == tree[k].r && tree[k].l == i) {
    tree[k].max_ = v;
    return;
  }

  int mid = tree[k].l + tree[k].r >> 1;
  if(i <= mid) {
    update(lc, i, v);    // 在左子树
  } else {
    update(rc, i, v);    // 在右子树
  }

  // 回归时更新最值
  tree[k].max_ = max(tree[lc].max_, tree[rc].max_);
}

// 查询区间 [l, r]的最大值
// 将 [l, r]看作一张大网, 找到其覆盖的所有区间的最大值
int query_max(int k, int l, int r) {
  // 区间覆盖
  // 第一次 k一定等于1, 网即使过大超过了数组大小 也不影响结果
  if(tree[k].l >= l && tree[k].r <= r)
    return tree[k].max_;

  int mid = tree[k].l + tree[k].r >> 1;
  int max__ = -inf;    // 局部变量
  if(l <= mid)    // 网捞左子树的最大值
    max__ = max(max__, query_max(lc, l, r));    // 大网不变
  if(r > mid)
    max__ = max(max__, query_max(rc, l, r));

  return max__;
}

// 查询区间 [l, r]的最大值, 方法二
// 网越缩越小
int query_max2(int k, int l, int r) {
  // 区间相等
  if(tree[k].l == l && tree[k].r == r)
    return tree[k].max_;

  int mid = tree[k].l + tree[k].r >> 1;  
  if(r <= mid)    // 左子树查询
    return query_max2(lc, l, r);
  else if(l > mid)    // 右子树查询
    return query_max2(rc, l, r);
  else    // 左右子树分别查询(缩小范围)
    return max(query(lc, l, mid), query_max2(rc, mid + 1, r);
}

AcWing 1275. 最大数

#include 
<iostream>
#include 
<cstring>
#include 
<algorithm>

#define lc k << 1
#define rc k << 1 | 1

using namespace std;
using LL = long long;

const int N = 2e5 + 10;

int m, p;
struct Node {
    int l, r;
    int v;  // 区间 [l, r]中的最大值 
}tr[N * 4];

void build(int k, int l, int r) {
    tr[k].l = l;
    tr[k].r = r;

    if(l == r) {
        // tr[k].v = 0;
        return;
    }

    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);

    // tr[k].v = max(tr[lc].v, tr[rc].v);
}

void update(int k, int i, int v) {
    if(tr[k].l == i && tr[k].r == i) {
        tr[k].v = v;
        return;
    }

    int mid = tr[k].l + tr[k].r >> 1;
    if(i <= mid) update(lc, i, v);
    else update(rc, i, v);

    tr[k].v = max(tr[lc].v, tr[rc].v);
}

int query(int k, int l, int r) {
    if(tr[k].l == l && tr[k].r == r)
        return tr[k].v;

    int mid = tr[k].l + tr[k].r >> 1;
    if(r <= mid) return query(lc, l, r);
    else if(l > mid) return query(rc, l, r);
    else return max(query(lc, l, mid), query(rc, mid + 1, r));
}

int main() {
    int n = 0, last = 0;    
    cin >> m >> p;
    build(1, 1, m);

    int x;
    char op[2];
    while(m --) {
        scanf("%s%d", op, &x);
        if(*op == 'Q') {
            last = query(1, n - x + 1, n);
            cout << last << endl;
        } else {
            update(1, n + 1, ((LL)last + x) % p);
            ++n;
        }
    }

    return 0;
}