摘要
Title: 1275. 最大数
Tag: 线段树
Memory Limit: 64 MB
Time Limit: 1000 ms

1275. 最大数

题意

给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1之间。
可以对这列数进行两种操作：
添加操作：向序列后添加一个数，序列长度变成 n+1；
询问操作：询问这个序列中最后 L个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
思路

添加操作：向序列后添加一个数，序列长度变成 n+1
- 可以这么实现：先用线段树开好空间，记录一个cnt代表加入的数字个数，每次加入时，挨着往后进行单点更新即可
剩下的就是线段树板子题，单点修改 + 区间查询

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-03-28 17:02:48
* @FilePath: \Acwing\1275\1275.cpp
* @LastEditTime: 2023-03-28 17:18:54
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;
#define ls p << 1
#define rs p << 1 | 1

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

struct sa
{
    int l, r, mx;
} tr[N << 2];

void pushup(int p)
{
    tr[p].mx = max(tr[ls].mx, tr[rs].mx);
}

void build(int p, int l, int r)
{
    tr[p] = {l, r, 0};
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

void update(int p, int L, int v)
{
    if (tr[p].l == L && tr[p].r == L)
    {
        tr[p].mx = v;
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if (L <= mid)
        update(ls, L, v);
    if (L > mid)
        update(rs, L, v);
    pushup(p);
}

int query(int p, int L, int R)
{
    if (tr[p].l >= L && tr[p].r <= R)
    {
        return tr[p].mx;
    }
    int res = 0;
    int mid = tr[p].l + tr[p].r >> 1;
    if (L <= mid)
        res = max(res, query(ls, L, R));
    if (R > mid)
        res = max(res, query(rs, L, R));
    return res;
}

int m, p, cnt, a;
signed main()
{
    IOS;
    cin >> m >> p;
    build(1, 1, m);
    while (m--)
    {
        char op;
        int t;
        cin >> op >> t;
        if (op == 'A')
        {
            update(1, ++cnt, (t + a) % p);
        }
        else
        {
            a = query(1, max(1LL, cnt - t + 1), cnt);
            cout << a << '\n';
        }
    }
    return 0;
}

1275. 最大数

题意

思路

代码