#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// Define long long for convenience
//#define int long long
#define ll long long
/**
* @struct DynamicSegTree2D
* @brief Implements a 2D Dynamic Segment Tree.
*
* This data structure is useful for performing 2D range queries (e.g., sum, min, max)
* and point updates on a very large or sparse 2D grid. It avoids allocating
* memory for the entire grid by creating nodes only when they are needed.
*
* The structure is essentially a dynamic segment tree of dynamic segment trees.
* The "outer" or "x-tree" segments the rows (first dimension), and each of its nodes
* contains a pointer to another "inner" or "y-tree" that segments the columns
* (second dimension) for that row range.
*
* @tparam T The data type of the values stored in the tree.
* @tparam M The merge operation function (e.g., plus, minimum, maximum).
*/
struct DynamicSegTree2D {
// The default value for nodes that don't exist and for query results on empty ranges.
ll DEFAULT_VALUE;
/**
* @brief Merges two values. This is the core operation of the segment tree.
* @param a The first value.
* @param b The second value.
* @return The result of merging a and b.
*/
ll merge(ll a, ll b) {
return gcd(a, b);
}
// --- Inner Segment Tree (for columns/y-axis) ---
struct NodeY {
ll val;
NodeY *left = nullptr, *right = nullptr;
NodeY(ll v = 0) : val(v) {}
// Safely get value from a node, returning default if null
ll left_val() { return left ? left->val : 0; }
ll right_val() { return right ? right->val : 0; }
};
// --- Outer Segment Tree (for rows/x-axis) ---
struct NodeX {
NodeY* y_tree = nullptr; // Pointer to the root of the column segment tree
NodeX *left = nullptr, *right = nullptr;
};
NodeX* root;
ll min_x, max_x, min_y, max_y;
/**
* @brief Constructor for the 2D Dynamic Segment Tree.
* @param min_coord_x The minimum possible x-coordinate.
* @param max_coord_x The maximum possible x-coordinate.
* @param min_coord_y The minimum possible y-coordinate.
* @param max_coord_y The maximum possible y-coordinate.
*/
DynamicSegTree2D(ll min_coord_x, ll max_coord_x, ll min_coord_y, ll max_coord_y)
: min_x(min_coord_x), max_x(max_coord_x), min_y(min_coord_y), max_y(max_coord_y) {
root = new NodeX();
DEFAULT_VALUE = 0;
}
DynamicSegTree2D(){}
// --- Update Functions ---
/**
* @brief Updates the value in the inner y-tree (columns).
*/
void update_y(NodeY*& node, ll y, ll val, ll cur_min_y, ll cur_max_y) {
if (!node) {
node = new NodeY();
}
if (cur_min_y == cur_max_y) {
node->val = val; // Update the value at the target y-coordinate
return;
}
ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
if (y <= mid_y) {
update_y(node->left, y, val, cur_min_y, mid_y);
} else {
update_y(node->right, y, val, mid_y + 1, cur_max_y);
}
node->val = merge(node->left_val(), node->right_val());
}
/**
* @brief Updates the value in the outer x-tree (rows), propagating to the y-trees.
*/
void update_x(NodeX*& node, ll x, ll y, ll val, ll cur_min_x, ll cur_max_x) {
if (!node) {
node = new NodeX();
}
// Update the corresponding y-tree at this x-node
update_y(node->y_tree, y, val, min_y, max_y);
if (cur_min_x == cur_max_x) {
return;
}
ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
if (x <= mid_x) {
update_x(node->left, x, y, val, cur_min_x, mid_x);
} else {
update_x(node->right, x, y, val, mid_x + 1, cur_max_x);
}
}
/**
* @brief Public interface for updating a value at a specific (x, y) coordinate.
* @param x The x-coordinate.
* @param y The y-coordinate.
* @param val The value to add.
*/
void update(ll x, ll y, ll val) {
update_x(root, x, y, val, min_x, max_x);
}
// --- Query Functions ---
/**
* @brief Performs a range query on the inner y-tree (columns).
*/
ll query_y(NodeY* node, ll y1, ll y2, ll cur_min_y, ll cur_max_y) {
if (!node || y1 > cur_max_y || y2 < cur_min_y) {
return DEFAULT_VALUE;
}
if (y1 <= cur_min_y && y2 >= cur_max_y) {
return node->val;
}
ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
ll left_res = query_y(node->left, y1, y2, cur_min_y, mid_y);
ll right_res = query_y(node->right, y1, y2, mid_y + 1, cur_max_y);
return merge(left_res, right_res);
}
/**
* @brief Performs a range query on the outer x-tree (rows).
*/
ll query_x(NodeX* node, ll x1, ll x2, ll y1, ll y2, ll cur_min_x, ll cur_max_x) {
if (!node || x1 > cur_max_x || x2 < cur_min_x) {
return DEFAULT_VALUE;
}
if (x1 <= cur_min_x && x2 >= cur_max_x) {
// This node's x-range is fully contained, so query its y-tree
return query_y(node->y_tree, y1, y2, min_y, max_y);
}
ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
ll left_res = query_x(node->left, x1, x2, y1, y2, cur_min_x, mid_x);
ll right_res = query_x(node->right, x1, x2, y1, y2, mid_x + 1, cur_max_x);
return merge(left_res, right_res);
}
/**
* @brief Public interface for a 2D range query.
* @param x1 The starting x-coordinate of the query rectangle.
* @param y1 The starting y-coordinate of the query rectangle.
* @param x2 The ending x-coordinate of the query rectangle.
* @param y2 The ending y-coordinate of the query rectangle.
* @return The aggregated value in the specified rectangle.
*/
ll query(ll x1, ll y1, ll x2, ll y2) {
return query_x(root, x1, x2, y1, y2, min_x, max_x);
}
~DynamicSegTree2D() {
// Destructor to clean up memory
delete_tree(root);
}
void delete_tree(NodeX* node) {
if (!node) return;
delete_tree(node->left);
delete_tree(node->right);
delete node->y_tree; // Clean up the y-tree
delete node;
}
};
DynamicSegTree2D st;
void init(int R, int C) {
st = DynamicSegTree2D(0, R, 0, 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, K;
// cin >> P >> Q >> K;
// update(P, Q, K);
// } else if (type == 2) {
// int P, Q, U, V;
// cin >> P >> Q >> U >> V;
// cout << calculate(P, Q, U, V) << '\n';
// }
// }
// }
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// solve();
// return 0;
// }
