#include "game.h"
#include <numeric> // For std::gcd
#include <algorithm> // For std::min/max
using namespace std;
#define ll long long
// Forward declaration
struct DynamicSegTree2D;
// Global pointer to our tree instance
static DynamicSegTree2D* st = nullptr;
static int R_dim, C_dim;
ll gcd_wrapper(ll a, ll b) {
if (a == 0) return b;
if (b == 0) return a;
return std::gcd(a, b);
}
/**
* @struct DynamicSegTree2D
* @brief Correctly implements a 2D Dynamic Segment Tree using bottom-up updates.
*
* This structure is a segment tree over rows (NodeX), where each node
* contains a pointer to a segment tree over columns (NodeY).
*/
struct DynamicSegTree2D {
static constexpr ll DEFAULT_VALUE = 0;
ll merge(ll a, ll b) {
return gcd_wrapper(a, b);
}
// --- Inner Segment Tree (for columns) ---
struct NodeY {
ll val = DEFAULT_VALUE;
NodeY *left = nullptr, *right = nullptr;
~NodeY() { // Destructor to prevent memory leaks
delete left;
delete right;
}
};
// --- Outer Segment Tree (for rows) ---
struct NodeX {
NodeY* y_tree = nullptr; // Pointer to the root of the column segment tree
NodeX *left = nullptr, *right = nullptr;
~NodeX() { // Destructor
delete y_tree;
delete left;
delete right;
}
};
NodeX* root = nullptr;
DynamicSegTree2D() {
root = new NodeX();
}
~DynamicSegTree2D() {
delete root;
}
// --- Update Functions ---
// Point update on a 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;
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);
}
ll left_val = node->left ? node->left->val : DEFAULT_VALUE;
ll right_val = node->right ? node->right->val : DEFAULT_VALUE;
node->val = merge(left_val, right_val);
}
// Point query on a Y-tree (columns)
ll query_y_point(NodeY* node, ll y, ll cur_min_y, ll cur_max_y) {
if (!node || cur_min_y > y || cur_max_y < y) {
return DEFAULT_VALUE;
}
if (cur_min_y == cur_max_y) {
return node->val;
}
ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
if (y <= mid_y) {
return query_y_point(node->left, y, cur_min_y, mid_y);
} else {
return query_y_point(node->right, y, mid_y + 1, cur_max_y);
}
}
// Main update function for the X-tree (rows)
void update_x(NodeX*& node, ll x, ll y, ll val, ll cur_min_x, ll cur_max_x) {
if (!node) {
node = new NodeX();
}
if (cur_min_x == cur_max_x) {
// We are at a leaf in the row tree, update its column tree
update_y(node->y_tree, y, val, 1, C_dim);
return;
}
// Recurse down to find the correct row leaf
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);
}
// *** THE CRITICAL STEP (BOTTOM-UP PROPAGATION) ***
// After child is updated, query children to update this node's column tree
ll left_y_val = node->left ? query_y_point(node->left->y_tree, y, 1, C_dim) : DEFAULT_VALUE;
ll right_y_val = node->right ? query_y_point(node->right->y_tree, y, 1, C_dim) : DEFAULT_VALUE;
update_y(node->y_tree, y, merge(left_y_val, right_y_val), 1, C_dim);
}
// --- Query Functions ---
// Range query on a Y-tree (columns)
ll query_y_range(NodeY* node, ll y1, ll y2, ll cur_min_y, ll cur_max_y) {
if (!node || y1 > y2 || 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_range(node->left, y1, min(y2, mid_y), cur_min_y, mid_y);
ll right_res = query_y_range(node->right, max(y1, mid_y + 1), y2, mid_y + 1, cur_max_y);
return merge(left_res, right_res);
}
// Main query function for the 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 > x2 || x1 > cur_max_x || x2 < cur_min_x) {
return DEFAULT_VALUE;
}
if (x1 <= cur_min_x && x2 >= cur_max_x) {
// This node's row-range is fully contained, query its column-tree
return query_y_range(node->y_tree, y1, y2, 1, C_dim);
}
ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
ll left_res = query_x(node->left, x1, min(x2, mid_x), y1, y2, cur_min_x, mid_x);
ll right_res = query_x(node->right, max(x1, mid_x + 1), x2, y1, y2, mid_x + 1, cur_max_x);
return merge(left_res, right_res);
}
};
// --- Interface Functions ---
void init(int R, int C) {
R_dim = R;
C_dim = C;
delete st; // Delete old tree if it exists
st = new DynamicSegTree2D();
}
void update(int P, int Q, long long K) {
if (st) {
st->update_x(st->root, P + 1, Q + 1, K, 1, R_dim);
}
}
long long calculate(int P, int Q, int U, int V) {
if (st) {
return st->query_x(st->root, P + 1, U + 1, Q + 1, V + 1, 1, R_dim);
}
return 0;
}
