算法提高课汇总

算法思路

题目需要动态添加节点, 而常规的线段树 操作并不支持动态添加节点.
考虑先创建区间范围足够大且元素值为$0$的线段树, 后续添加节点的操作
可以看作是对添加位置的节点元素值的修改操作. 此时题目需要两种操作:

• 修改单个元素

• 查询区间元素最大值

代码实现

实现时注意添加数值为两个int型数值的和, 存在溢出风险.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

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);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if ( l == r )
    {//叶节点数值为对应元素数值
        //tr[u].v = 0;
        return;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        //pushup(u) 由于初始数值均为0 可以忽略节点的赋值
    }
}

int query(int u, int l, int r)
{
    if ( l <= tr[u].l && tr[u].r <= r ) return tr[u].v;

    int v = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if ( l <= mid ) v = query(u << 1, l, r);
    if ( r >= mid + 1) v = max(v, query(u << 1 | 1, l, r));
    return v;
}

void modify(int u, int x, int v)
{
    if ( tr[u].l == tr[u].r )
    {//叶节点 直接修改
        tr[u].v = v;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if ( x <= mid ) modify(u << 1, x, v);
        else    modify(u << 1 | 1, x, v);
        pushup(u);  //将新信息向上传递
    }
}

int main()
{
    scanf("%d%d", &m, &p);
    build(1, 1, m); //最多有m个添加操作

    int x;
    char op[2];
    int last = 0, n = 0;
    while ( m -- )
    {
        scanf("%s%d", op, &x);
        if ( *op == 'Q' )
        {
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        }
        else
        {
            n ++ ;
            modify(1, n, ( (ll)x + last ) % p);
        }
    }
    return 0;
}