【题解】最大数

线段树

线段树

1. 线段树是在一维数组上，通过堆的方式实现的树状数据结构。主要支持区间修改、区间查询两大操作，其余的单点修改和单点查询等可以视为区间操作的简单化。

题目链接：最大数

线段树

1. 线段树是在一维数组上，通过堆的方式实现的树状数据结构。主要支持区间修改、区间查询两大操作，其余的单点修改和单点查询等可以视为区间操作的简单化。
2. 为了实现上述操作，线段树有两个最基本的函数：pushup 和 pushdow ，前者通过子节点修改父节点的信息，后者通过父节点向下递归修改子节点的信息。通常 pushup 会用在建树函数或修改函数的回溯过程中用到。
3. 通常情况下线段树会包含四个基本函数：①.pushup 函数：。②.build 函数：将一段区间初始化为线段树。③.modify 函数：修改单点或区间信息，如果是后者，则需要用到 pushdown 函数和懒标记（ lazy ）。④.query 函数：查询某段区间的信息。
4. 线段树是一棵满二叉树，若某个节点的编号为 x ，则其父节点的编号为 x >> 1，其左右子节点的编号分别为 x << 1 和 x << 1 | 1 。在开辟空间时需要开 4 * N 的空间，以防溢出（实际所用的空间一定严格小于 4 * N ）。

本题细节

1. 由于最多有 m 个询问，所以线段树所维护的原序列长度最多为 m 。
2. 在查询和修改函数中，mid 都是指当前节点所维护区间的中点，而不是询问的目标区间中点。
3. 查询函数在递归是，目标区间的左右端点不能改变，必须一直是 [l, r] ，否则会导致查询的区间长度异常。原因：这里的 mid 是通过 tr[u].l + tr[u].r >> 1 算出来的，不能确定 mid 和 l、r 的大小关系，例如我要查询的目标区间是 [3, 4] ，从 [1, 10] 中找，由于不符合查询函数的第一个 if 条件，需要递归，如果 else 里的第一个 if 对应的区间改成 [l,mid] ，那查询的范围就成 [3,5] 了。
4. 查询完后务必记得 n ++ ; 。
5. 由于本题中 build 函数建立的是一棵空线段树，所以不需要 pushup 操作。
6. 插入新的数据时，需要提前转为 long long 类型。

线段树 c++ 705ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 5;

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

// 由子节点的信息，来计算父节点的信息
void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

// u是线段树每个节点在一维数组中的映射
// l和r表示该节点所包含原序列的区间左右端点
void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

// u是线段树每个节点在一维数组中的映射
// l和r表示所要查询的目标区间
int query(int u, int l, int r)
{
    // 如果当前节点的左右端点在目标区间内部，则直接返回
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].v;
    else 
    {
        // 注意mid由tr[u].l和tr[u].r计算得到
        int mid = tr[u].l + tr[u].r >> 1;
        int v = 0;
        if (l <= mid) v = query(u << 1, l, r);
        if (r > mid) v = max(v, query(u << 1 | 1, l, r));
        return v;
    }
}

// 单点修改，将原序列下标为x的点的值修改为y
void modify(int u, int x, int y)
{
    // 首先确保遍历到叶节点，其次该叶节点要对应修改点的下标
    if (tr[u].l == tr[u].r && tr[u].l == x) tr[u].v = y;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x > mid) modify(u << 1 | 1, x, y);
        else modify(u << 1, x, y);
        // 修改完叶节点的值后要回溯修改父节点
        pushup(u);
    }
}

int main()
{
    cin >> m >> p;
    build(1, 1, m);

    int n = 0, a = 0;
    while (m -- )
    {
        char op[2];
        int t;
        scanf("%s%d", op, &t);
        if (*op == 'Q')
        {
            a = query(1, n - t + 1, n);
            printf("%d\n", a);
        }
        else 
        {
            t = ((LL)a + t) % p;
            modify(1, n + 1, t);
            // 务必记得n+1
            n ++ ;
        }
    }
    return 0;
}