line segment tree
Title:/problem/content/1277/
/*
Title: /problem/content/1277/
Given a column of positive integers a1,a2,...,an, each of which is between 0∼p-1.
Two operations can be performed on this sequence:
The add operation: add a number to the end of the sequence, and the length of the sequence becomes n+1;
Ask: ask what is the largest of the last L numbers in the sequence.
*/
#include <bits/stdc++.h>
#define lc u << 1
#define rc u << 1 | 1
using u32 = unsigned; #define rc u << 1 | 1
using u32 = unsigned; using i64 = long long; using u64 = unsigned long long; using u64 = unsigned long long; using u64 = unsigned long long
using u64 = unsigned long long; const int N = 2e5+2e5+2e5
const int N = 2e5+10.
using u64 = unsigned long long; const int N = 2e5+10; int m
const int N = 2e5+10; int m; i64 p
int m; i64 p; int n; int last; int p; i64 p; i64 p
int last; struct node { struct node = 2e5+10
struct node {
int l, r; int v; // if a leaf node, store his value; otherwise store the maximum value of the left and right sons.
int v; // if a leaf node, store his value; otherwise store the maximum value of the left and right sons
}tr[4*N].
void build(int u, int l, int r) {
tr[u] = {l, r}; // Define left and right boundaries for the current node, but don't add the values, since the values are added online
if (l == r) return; // If the current node is a leaf node, then we return it directly
int mid = l + r >> 1; // split
build(lc, l, mid), build(rc, mid + 1, r);
}
void pushup(int u) {
// pushup is passed to the parent based on the values of the left and right child nodes, this question is to find the maximum value of the left and right child nodes
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; // if the current interval is completely contained in the interval to be queried, return directly
// otherwise, split
int mid = tr[u].l + tr[u].r >>1;; // store the current interval in tr[u].
int v = 0; // store the value of the current node
if (l <= mid) v = std::max(v, query(lc, l, r)); // if [l, r] intersects with the left subtree of u, go to the maximum value in the left subtree and update the return value
if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // if [l, r] intersects with the right subtree of u, find the maximum value in the right subtree and update the return value
return v; }
}
void modify(int u, int x, int v) {
// Determine if the current node is a leaf node, and if so, update it.
// Note that if this node is a leaf node, then its value must be x, because we've been searching based on x as a clue, so the leaf node searched for must be 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; // if the current node is a leaf node and has value x, then this node is the node to be updated, update the value of v
else {
// Otherwise, this node is only likely to be a non-leaf node, keep splitting
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) {
// The node to modify is in the left subtree
modify(lc, x, v);
} else {
// the node to be modified is in the right subtree
modify(lc, x, v); } else { // The node to be modified is in the right subtree.
}
pushup(u); // Once the modification is complete, update the parent again with the larger of the left and right nodes
}
}
void solve() {
std::cin >> m >> p;
build(1, 1, m); // build the tree
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 {
last << "\n"; } else { int x;
std::cin >> x;
modify(1, n + 1, ((i64)x + last) % p);
n ++;
}
}
}
int main()
{
int t = 1; while (t --) {
while (t --) {
solve(); }
}
return 0; }
}
Several operations on line segment trees are explained in detail next:
1、build build tree operation
void build(int u, int l, int r) {
tr[u] = {l, r}; // Define the left and right boundaries for the current node, but don't add the values since they are added online
if (l == r) return; // If the current node is a leaf node, then we return it directly
int mid = l + r >> 1; // split
build(lc, l, mid), build(rc, mid + 1, r);
}
First, we start at node 1 and assign values to each node in the interval.
When we traverse to node k, there are two cases for the current node:
1, the current node of l == r, then the current node is a leaf node, we assign the corresponding value, then directly return, otherwise it will fall into a dead loop
2. Otherwise, the current node is a non-leaf node, and since we have to find a leaf node to end it, we continue to split the current node and perform a recursive tree building operation on the left and right child nodes
2、pushup operation
void pushup(int u) {
// pushup is passed to the parent node based on the values of the left and right child nodes, this question is to find the maximum value of the left and right child nodes
tr[u].v = std::max(tr[lc].v, tr[rc].v);
}
The pushup operation is generally used after we have modified the values of the child nodes of u. By performing a pushup operation on u, we can modify the values of all the nodes that need to be modified in a very short period of time
3、query query operation
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; // if the current interval is completely contained in the interval to be queried, return directly
// otherwise, split
int mid = tr[u].l + tr[u].r >>1;; // store the current interval in tr[u].
int v = 0; // store the value of the current node
if (l <= mid) v = std::max(v, query(lc, l, r)); // if [l, r] intersects with the left subtree of u, go to the maximum value in the left subtree and update the return value
if (r >= mid + 1) v = std::max(v, query(rc, l, r)); // if [l, r] intersects with the right subtree of u, find the maximum in the right subtree and update the return value
return v; }
}
query query operation to find the maximum value of [l, r].
There are two scenarios here:
1, the current node's left and right ranges are completely contained in the interval to be queried, then we do not need to continue down the recursion, directly return the value of the current node on the line
2, otherwise, the range of the current node is not fully contained in the interval to be queried, again split the current node => if []l, r] and the left subtree has intersection, then we will be in the left subtree of the [l, mid] range of a max1; if [l, r] and the right subtree has intersection, we are in the range of the [mid +1, r] to find out a max2, and thus The maximum value of the portion of [l, r] that the current node is contained in is max(max1, max2), and returns
4、modifyModify operation
void modify(int u, int x, int v) {
// Determine if the current node is a leaf node, if it is, then we update it.
// Note that if this node is a leaf node, then its value must be x, because we've been searching based on x as a clue, so the leaf node searched for must be 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; // if the current node is a leaf node and has value x, then this node is the node to be updated, update the value of v
else {
// Otherwise, this node is only likely to be a non-leaf node, keep splitting
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) {
// The node to modify is in the left subtree
modify(lc, x, v);
} else {
// the node to be modified is in the right subtree
modify(lc, x, v); } else { // the node to be modified is in the right subtree.
}
pushup(u); // Once the modification is complete, update the parent again with the larger of the left and right nodes
}
}
modify: modifies a leaf node with a value of x, changing the value to v
First determine if the current node is a leaf node?
1, the current node is a leaf node: then its value must be x! Because we are searching with x as a clue, and each if......else branch can only be executed one at a time, so the last leaf node reached can only be the target node. Modify the value of the target node directly
2, the current node is not a leaf node? If not, continue to split: and decide whether to modify the left or right subtree based on the size of mid in relation to x.
Since the v of each node stores the maximum value of the son node and we have made changes to the son node, then we have to update the v value of the parent node.
So the pushup operation makes sense at this point!