线段树
线段树
标题：https://www.acwing.com/problem/content/1277/
/*
标题：https://www.acwing.com/problem/content/1277/
给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作：
增加操作：向序列后增加一个数，序列长度变成 n+1；
问询操作：问询这个序列中最终 L 个数中最大的数是多少。
*/
#include <bits/stdc++.h>
#define lc u << 1
#define rc u << 1 | 1
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
const int N = 2e5+10;
int m;
i64 p;
int n;
int last;
struct node {
int l, r;
int v; // 假如是叶子节点，存储他的值；不然存储左右儿子的最大值
}tr[4*N];
void build(int u, int l, int r) {
tr[u] = {l, r}; // 为当时节点界说左右鸿沟，可是不参加值，因为值是在线参加的
if (l == r) return; // 假如当时节点是叶子节点，那么咱们就直接回来
int mid = l + r >> 1; // 裂开
build(lc, l, mid), build(rc, mid + 1, r);
}
void pushup(int u) {
// pushup是依据左右子节点的值传递给父节点，这道题是求左右子节点的最大值
tr[u].v = std::max(tr[lc].v, tr[rc].v);
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; // 假如当时区间彻底包括在要查询的区间中，直接回来
// 不然，裂开
int mid = tr[u].l + tr[u].r >> 1;
int v = 0; // 存储当时节点的值
if (l <= mid) v = std::max(v, query(lc, l, r)); // 假如[l, r]与u的左子树有交集，就去找左子树中的最大值，而且更新回来值
if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // 假如[l, r]与u的右子树有交集，就去找右子树中的最大值，而且更新回来值
return v;
}
void modify(int u, int x, int v) {
// 判别当时节点是不是叶子节点，假如是叶子节点，那么咱们就直接更新
// 需求留意的是，假如这个节点是叶子节点，那么它的值一定是x，因为咱们一直是依据x作为头绪来进行查找的，所以查找到的叶子节点一定是x
// if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
if (tr[u].l == tr[u].r) tr[u].v = v;// 假如当时节点是叶子节点而且值为x，那么此节点便是待更新的节点，更新v的值
else {
// 不然，这个节点就只或许对错叶子节点，持续裂开
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) {
// 要修正的节点在左子树
modify(lc, x, v);
} else {
// 要修正的节点在右子树
modify(rc, x, v);
}
pushup(u); // 修正完结之后，再次把左右节点的较大值更新到父节点
}
}
void solve() {
std::cin >> m >> p;
build(1, 1, m); // 建树
char op[2];
while (m --) {
scanf("%s", op);
if (*op == 'Q') {
int l;
std::cin >> l;
last = query(1, n - l + 1, n);
std::cout << last << "\n";
} else {
int x;
std::cin >> x;
modify(1, n + 1, ((i64)x + last) % p);
n ++;
}
}
}
int main()
{
int t = 1;
while (t --) {
solve();
}
return 0;
}
接下来对线段树的几个操作进行详解：
1、build建树操作
void build(int u, int l, int r) {
tr[u] = {l, r}; // 为当时节点界说左右鸿沟，可是不参加值，因为值是在线参加的
if (l == r) return; // 假如当时节点是叶子节点，那么咱们就直接回来
int mid = l + r >> 1; // 裂开
build(lc, l, mid), build(rc, mid + 1, r);
}
首要，咱们从节点1开端，为区间的每个节点赋值。
当咱们遍历到节点k，当时节点有两种状况：
1、当时节点的l == r，那么当时节点便是叶子节点，咱们对其赋相应的值之后，就直接回来，不然会堕入死循环
2、不然，当时节点便对错叶子节点，因为咱们要找到叶子节点才干完毕，所以咱们对当时节点持续割裂，对左右子节点进行递归建树操作
2、pushup操作
void pushup(int u) {
// pushup是依据左右子节点的值传递给父节点，这道题是求左右子节点的最大值
tr[u].v = std::max(tr[lc].v, tr[rc].v);
}
pushup操作一般用于咱们修正了u的子节点的值之后，对u进行Pushup操作，就可以在十分短的时间内对一切需求做出修正的节点的值进行修正
3、query查询操作
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; // 假如当时区间彻底包括在要查询的区间中，直接回来
// 不然，裂开
int mid = tr[u].l + tr[u].r >> 1;
int v = 0; // 存储当时节点的值
if (l <= mid) v = std::max(v, query(lc, l, r)); // 假如[l, r]与u的左子树有交集，就去找左子树中的最大值，而且更新回来值
if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // 假如[l, r]与u的右子树有交集，就去找右子树中的最大值，而且更新回来值
return v;
}
query查询操作，求出[l, r]的最大值
此处有两种状况：
1、当时节点的左右规模彻底包括在需求查询的区间中，那么咱们就没必要再持续往下递归，直接回来当时节点的值就行了
2、不然，当时节点的规模没有彻底包括到需求查询的区间中，再次对当时节点进行割裂 =>假如[]l, r]与左子树有交集，那么咱们就在左子树的[l, mid]规模内求出一个max1；假如[l, r]与右子树有交集，咱们在[mid+1, r]规模内求出一个max2，所以当时节点包括在[l, r]中那部分的最大值便是max(max1, max2)，然后回来
4、modify修正操作
void modify(int u, int x, int v) {
// 判别当时节点是不是叶子节点，假如是叶子节点，那么咱们就直接更新
// 需求留意的是，假如这个节点是叶子节点，那么它的值一定是x，因为咱们一直是依据x作为头绪来进行查找的，所以查找到的叶子节点一定是x
// if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
if (tr[u].l == tr[u].r) tr[u].v = v;// 假如当时节点是叶子节点而且值为x，那么此节点便是待更新的节点，更新v的值
else {
// 不然，这个节点就只或许对错叶子节点，持续裂开
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) {
// 要修正的节点在左子树
modify(lc, x, v);
} else {
// 要修正的节点在右子树
modify(rc, x, v);
}
pushup(u); // 修正完结之后，再次把左右节点的较大值更新到父节点
}
}
modify：对某个值为x的叶子节点进行修正，把值改为v
首要判别当时节点是不是叶子节点？
1、当时节点是叶子节点：那么它的值就一定是x！为什么呢？因为咱们是以x为头绪进行查找的，而且每次的if……else分支只能履行一个，所以最终抵达的叶子节点就只能是方针节点。直接对方针节点的值进行修正
2、当时节点不是叶子节点呢？不是的话，持续割裂：而且依据mid与x的巨细联系决定是修正左子树仍是右子树。
因为每个节点的v存储的是儿子节点的最大值，而且咱们对儿子节点进行修正了，那么咱们就要更新父节点的v值。
所以pushup操作在此刻有了含义！
