P1198 [JSOI2008] 最大数

题目

P1198 [JSOI2008] 最大数

算法标签: 数据结构, 线段树, ST表

思路

很明显操作是查询一个区间, 修改单点位置, 可以使用非懒标记的线段树 维护序列, 或者使用$ST$表查询, 算法时间复杂度$O(n\log n)$

代码

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

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
const LL INF = (LL) ((LL) 1 << 63) - 1;

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

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

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

LL query(int u, int ql, int qr) {
   
    if (tr[u].l >= ql && tr[u].r <= qr) {
   
        return tr[u].val;
    }
    LL ans = -INF;
    int mid = tr[u].l + tr[u].r >> 1;
    if (ql <= mid) ans = max(ans, query(u << 1, ql, qr));
    if (qr > mid) ans = max(ans, query(u << 1 | 1, ql, qr));
    push_up(u);
    return ans;
}

void modify(int u, int pos, int val) {
   
    if (tr[u].l == pos && tr[u].r == pos) {
   
        tr[u].val = val;
        return;
    }

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

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

    LL last = 0;
    cin >> m >> mod;
    build(1, 1, m);

    char op;
    LL val;
    int cnt = 0;
    while (m--) {
   
        cin >> op >> val;
        if (op == 'Q') {
   
            int ans;
            if (cnt == 0) ans = 0;
            //查询最后val个数
            else ans = query(1, cnt - val + 1, cnt);
            last = ans;
            cout << ans << "\n";
        }
        else {
   
            val = (LL) (val + last) % mod;
            modify(1, cnt + 1, val);
            cnt++;
        }
    }

    return 0;
}