#include "game.h"
#include<bits/stdc++.h>
using namespace std;
/**
* @struct SegTree2D
* @brief A memory-efficient 2D dynamic segment tree template.
*
* This data structure is designed for 2D point updates and range queries on a sparse
* grid. It is based on a segment tree of highly sparse segment trees, making it
* extremely memory-efficient for problems with large coordinate spaces but
* a relatively small number of points.
*
* @tparam T The data type of the values stored in the tree (e.g., long long, int).
*/
template<typename T>
struct SegTree2D {
private:
// --- Data Members ---
int R_min_dim, R_max_dim, C_min_dim, C_max_dim;
T default_value;
// --- Nested Node Structs ---
// The inner tree for columns (y-axis). This is a highly sparse, custom segment tree.
struct X_NODE {
int s, e; // The range this node is responsible for [s, e]
X_NODE *left = nullptr, *right = nullptr;
T value;
X_NODE(int s, int e, T def_val) : s(s), e(e), value(def_val) {}
~X_NODE() {
delete left;
delete right;
}
};
// The outer tree for rows (x-axis).
struct Y_NODE {
Y_NODE *left = nullptr, *right = nullptr;
// Each row-node contains a root for a column-tree.
X_NODE xtree;
Y_NODE(int c_min, int c_max, T def_val) : xtree(c_min, c_max, def_val) {}
~Y_NODE() {
delete left;
delete right;
}
};
Y_NODE* root = nullptr;
int merge(int a, int b){
return gcd(a, b);
}
// --- Private Helper Functions (Recursive Logic) ---
// Update function for the inner/column tree (X_NODE)
void update_y(X_NODE* node, int q, T k) {
int s = node->s, e = node->e;
if (s == e) {
node->value = k;
return;
}
int m = s + (e - s) / 2;
X_NODE** child_ptr = (q <= m) ? &(node->left) : &(node->right);
if (*child_ptr == nullptr) {
*child_ptr = new X_NODE(q, q, default_value);
(*child_ptr)->value = k;
} else if ((*child_ptr)->s <= q && q <= (*child_ptr)->e) {
update_y(*child_ptr, q, k);
} else {
int new_s = s, new_e = e, new_m = m;
do {
if (q <= new_m) new_e = new_m;
else new_s = new_m + 1;
new_m = new_s + (new_e - new_s) / 2;
} while ((q <= new_m) == ((*child_ptr)->e <= new_m));
X_NODE* new_node = new X_NODE(new_s, new_e, default_value);
if ((*child_ptr)->e <= new_m) new_node->left = *child_ptr;
else new_node->right = *child_ptr;
*child_ptr = new_node;
update_y(*child_ptr, q, k);
}
T left_val = node->left ? node->left->value : default_value;
T right_val = node->right ? node->right->value : default_value;
node->value = merge(left_val, right_val);
}
// Point query for the inner/column tree, needed for bottom-up updates.
T query_y_point(X_NODE* node, int q) {
if (node == nullptr || node->s > q || node->e < q) {
return default_value;
}
if (node->s == node->e) {
return node->value;
}
int m = node->s + (node->e - node->s) / 2;
return (q <= m) ? query_y_point(node->left, q) : query_y_point(node->right, q);
}
// Range query for the inner/column tree.
T query_y_range(X_NODE* node, int s, int e) {
if (node == nullptr || node->s > e || node->e < s) {
return default_value;
}
if (s <= node->s && node->e <= e) {
return node->value;
}
return merge(query_y_range(node->left, s, e), query_y_range(node->right, s, e));
}
// Update function for the outer/row tree (Y_NODE)
void update_x(Y_NODE* node, int s, int e, int p, int q, T k) {
if (s == e) {
update_y(&node->xtree, q, k);
return;
}
int m = s + (e - s) / 2;
if (p <= m) {
if (node->left == nullptr) node->left = new Y_NODE(C_min_dim, C_max_dim, default_value);
update_x(node->left, s, m, p, q, k);
} else {
if (node->right == nullptr) node->right = new Y_NODE(C_min_dim, C_max_dim, default_value);
update_x(node->right, m + 1, e, p, q, k);
}
T left_val = node->left ? query_y_point(&node->left->xtree, q) : default_value;
T right_val = node->right ? query_y_point(&node->right->xtree, q) : default_value;
update_y(&node->xtree, q, merge(left_val, right_val));
}
// Query function for the outer/row tree (Y_NODE)
T query_x(Y_NODE* node, int s, int e, int p, int q, int u, int v) {
if (node == nullptr || s > u || e < p) {
return default_value;
}
if (p <= s && e <= u) {
return query_y_range(&node->xtree, q, v);
}
int m = s + (e - s) / 2;
return merge(query_x(node->left, s, m, p, q, u, v),
query_x(node->right, m + 1, e, p, q, u, v));
}
public:
/**
* @brief Constructs the 2D Segment Tree.
* @param r_min The minimum row coordinate.
* @param r_max The maximum row coordinate.
* @param c_min The minimum column coordinate.
* @param c_max The maximum column coordinate.
* @param def_val The default value for empty nodes (e.g., 0 for sum/gcd, infinity for min).
*/
SegTree2D(int r_min, int r_max, int c_min, int c_max, T def_val = T{})
: R_min_dim(r_min), R_max_dim(r_max), C_min_dim(c_min), C_max_dim(c_max), default_value(def_val) {
root = new Y_NODE(C_min_dim, C_max_dim, default_value);
}
SegTree2D(){}
~SegTree2D(){
delete root;
}
/**
* @brief Updates the value at a specific point in the grid.
* @param P The row.
* @param Q The column.
* @param K The new value for the point.
*/
void update(int P, int Q, T K) {
update_x(root, R_min_dim, R_max_dim, P, Q, K);
}
/**
* @brief Performs a range query on a rectangular area of the grid.
* @param P The starting row of the rectangle.
* @param Q The starting column of the rectangle.
* @param U The ending row of the rectangle.
* @param V The ending column of the rectangle.
* @return The aggregated value in the specified rectangle.
*/
T query(int P, int Q, int U, int V) {
return query_x(root, R_min_dim, R_max_dim, P, Q, U, V);
}
};
SegTree2D<int> st(0, 1e9, 0, 1e9);
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
st.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return st.query(P, Q, U, V);
}
// void solve(){
// int r, c, q;
// cin >> r >> c >> q;
// init(r, c);
// while(q--){
// int type;
// cin >> type;
// if(type == 1){
// int p, q, val;
// cin >> p >> q >> val;
// update(p, q, val);
// }else{
// int p, q, u, v;
// cin >> p >> q >> u >> v;
// cout << calculate(p, q, u, v) << "\n";
// }
// }
// }
// int main(){
// ios_base::sync_with_stdio(0), cin.tie(0);
// solve();
// return 0;
// }
