洛谷 P1198 [JSOI2008]最大数

题意简述

维护一个初始为空的数列，支持以下两种操作，操作共m次：
1.查询当前数列中末尾k个数中的最大的数。
2.将x插入到数列的末尾。

题解思路

维护一个线段树，支持单点修改，区间查询

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll m, x, k, t, mod, cnt;
ll a[400010];
char opt;
void push_up(ll x)
{
    a[x] = max(a[x << 1], a[x << 1 | 1]);
}
void add(ll x, ll l, ll r, ll n, ll k)
{
    if (l == r)
    {
        a[x] = k % mod;
        return;
    }
    ll mid = l + r >> 1;
    if (n <= mid) add(x << 1, l, mid, n, k);
    if (n >  mid) add(x << 1 | 1, mid + 1, r, n, k);
    push_up(x);
}
ll query(ll x, ll l, ll r, ll l1, ll r1, ll ans = 0)
{
    if (l1 <= l && r <= r1) return a[x];
    ll mid = l + r >> 1;
    if (l1 <= mid) ans = max(query(x << 1, l, mid, l1, r1), ans);
    if (r1 >  mid) ans = max(query(x << 1 | 1, mid + 1, r, l1, r1), ans);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> mod;
    for (register ll i = 1; i <= m; ++i)
    {
        cin >> opt >> x;
        if (opt == 'A') 
        {
            ++cnt;
            add(1, 1, m, cnt, (x + t) % mod);
        }
        else
        {
            t = query(1, 1, m, cnt - x + 1, cnt);
            cout << t << endl;
        }
    }
}

洛谷 P1198 [JSOI2008]最大数

原文：https://www.cnblogs.com/xuyixuan/p/9482082.html