基础数据结构应用-最大数

题目-最大数

问题分析

因为有$m$次操作, 并且修改序列的操作是在序列的最后添加一个数
因此可以先将即将添加进来的数据的位置初始化, 并且同步的记录序列的最后一个位置$n$, 如果添加数字, 将$n$指针向后移动

modify(1, n + 1, val);
n++;

算法步骤

• 确定线段树中存储的属性是$maxv$
• 读入操作数$m$, 构建线段树build(1, 1, m)
• 执行查询和修改操作

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int m, p;
struct Node {
   
    int l, r;
    LL maxv;
} tr[N << 2];

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

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

void modify(int u, LL x, LL val) {
   
    if (tr[u].l == tr[u].r) {
   
        tr[u].maxv = max(tr[u].maxv, val);
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(u << 1, x, val);
    if (x > mid) modify(u << 1 | 1, x, val);

    pushup(u);
}

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

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

    pushup(u);
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> p;

    build(1, 1, m);

    int n = 0;
    LL a = 0;
    while (m--) {
   
        char c;
        cin >> c;
        if (c == 'Q') {
   
            int L;
            cin >> L;
            LL ans = query(1, n - L + 1, n);
            cout << ans << '\n';
            a = ans;
        }
        else {
   
            int t;
            cin >> t;
            modify(1, n + 1, (LL) (t + a) % p);
            n++;
        }
    }

    return 0;
}