#include <bits/stdc++.h>
using namespace std;
// SparseSegtree is designed for very large ranges (for example up to 1e9)
// but only creates nodes for segments that are updated or queried.
// It supports range "set" updates (assigning a given value to every element in a range)
// and range sum queries.
class SparseSegtree {
private:
// Each node stores:
// - freq: the aggregate value (here, the sum of the segment)
// - lazy: a lazy propagation marker (nonzero means that the node’s segment
// should be updated to that value)
// - left, right: indices in the tree vector for the left and right children.
struct Node {
int freq = 0; // sum of the segment
int lazy = 0; // lazy marker for range-set updates; 0 means no pending update
int left = -1; // index of left child in the tree vector (-1 if not created)
int right = -1; // index of right child (-1 if not created)
};
vector<Node> tree; // the collection of nodes (dynamically allocated as needed)
const int n; // size of the overall range [0, n-1]
int timer = 0; // used to assign indices for new nodes
// Combine two segment values.
// For a sum query, simply add the two values.
inline int comb(int a, int b) {
return a + b;
}
// Apply a range-set update to the current node.
// 'cur' is the current node index.
// 'len' is the length of the segment represented by this node.
// 'val' is the value we want to assign over the entire segment.
inline void apply(int cur, int len, int val) {
// Set the lazy marker (indicating that the whole segment is updated to 'val')
tree[cur].lazy = val;
// Update the aggregate value (frequency) of this node.
tree[cur].freq = len * val;
}
// Propagate the lazy update from the current node down to its children.
// 'l' and 'r' represent the current segment boundaries.
inline void push_down(int cur, int l, int r) {
// Create left child if it doesn't exist
if (tree[cur].left == -1) {
tree[cur].left = ++timer;
tree.push_back(Node());
}
// Create right child if it doesn't exist
if (tree[cur].right == -1) {
tree[cur].right = ++timer;
tree.push_back(Node());
}
int m = (l + r) / 2; // mid-point of the segment
// If there is a pending lazy update on the current node, push it to both children.
if (tree[cur].lazy != 0) {
apply(tree[cur].left, m - l + 1, tree[cur].lazy);
apply(tree[cur].right, r - m, tree[cur].lazy);
// Clear the lazy marker after propagation.
tree[cur].lazy = 0;
}
}
// Internal function to perform a range-set update.
// It sets every element in the interval [ql, qr] to 'val'.
// cur: current node index; [l, r] is the segment for this node.
void range_set(int cur, int l, int r, int ql, int qr, int val) {
// No overlap: simply return.
if (qr < l || ql > r)
return;
// Total overlap: directly apply the update.
if (ql <= l && r <= qr) {
apply(cur, r - l + 1, val);
} else {
// Partial overlap: first push down any pending lazy updates.
push_down(cur, l, r);
int m = (l + r) / 2;
// Recurse to left child.
range_set(tree[cur].left, l, m, ql, qr, val);
// Recurse to right child.
range_set(tree[cur].right, m + 1, r, ql, qr, val);
// Combine results from children.
tree[cur].freq = comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
}
}
// Internal function to compute the range sum over [ql, qr].
// cur: current node index; [l, r] is the segment for this node.
int range_sum(int cur, int l, int r, int ql, int qr) {
// No overlap.
if (qr < l || ql > r)
return 0;
// Total overlap.
if (ql <= l && r <= qr)
return tree[cur].freq;
// Partial overlap: push down pending updates and combine query results.
push_down(cur, l, r);
int m = (l + r) / 2;
return comb(range_sum(tree[cur].left, l, m, ql, qr),
range_sum(tree[cur].right, m + 1, r, ql, qr));
}
public:
// Constructor:
// 'n' is the overall size of the range.
// 'q' (optional) is the expected number of queries, used to reserve space.
SparseSegtree(int n, int q = 0) : n(n) {
// Reserve extra space in the vector if a query count is given.
if (q > 0)
tree.reserve(2 * q * __lg(n));
// Create the root node which covers the whole range [0, n-1].
tree.push_back(Node());
}
// Public interface for range_set update:
// Sets all elements in the interval [ql, qr] to 'val'.
void range_set(int ql, int qr, int val) {
range_set(0, 0, n - 1, ql, qr, val);
}
// Public interface for range_sum query:
// Returns the sum of values in the interval [ql, qr].
int range_sum(int ql, int qr) {
return range_sum(0, 0, n - 1, ql, qr);
}
};
//////////////////////////
/// Main Program Demo ///
//////////////////////////
int main() {
int query_num;
cin >> query_num;
// In this example, we assume the overall range is 1e9 (rails numbered 0..1e9)
const int RANGE_SIZE = 1e9;
// Create the sparse segment tree.
// We add 1 to RANGE_SIZE to cover [0, RANGE_SIZE] and pass the query count to reserve space.
SparseSegtree st(RANGE_SIZE + 1, query_num);
// 'c' is used to adjust query indices based on previous query results (a common technique in interactive problems).
int c = 0;
for (int i = 0; i < query_num; i++) {
int type, x, y;
cin >> type >> x >> y;
// Query: when type == 1, perform a range sum query.
if (type == 1) {
// Adjust the query interval using c.
c = st.range_sum(x + c, y + c);
cout << c << '\n';
}
// Update: when type == 2, perform a range-set update.
// For the red-ripening event, the update value is 1.
else if (type == 2) {
st.range_set(x + c, y + c, 1);
}
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
