#include "game.h"
#include <bits/stdc++.h>
#define ll long long
// Use static global variables as in the accepted solution
static int R_max_dim, C_max_dim, R_min_dim, C_min_dim;
// Forward declarations
struct X_NODE;
struct Y_NODE;
// Global root pointer
static Y_NODE* root = nullptr;
// Wrapper for GCD to handle the case where one value is 0
ll merge(ll x, ll y) {
if (x == 0) return y;
if (y == 0) return x;
return std::gcd(x, y);
}
// The inner tree for columns. 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;
ll value = 0LL;
X_NODE(int s, int e) : s(s), e(e) {}
~X_NODE() {
delete left;
delete right;
}
};
// The outer tree for rows. This is a more standard dynamic segment tree.
struct Y_NODE {
Y_NODE *left = nullptr, *right = nullptr;
// Each row-node contains a root for a column-tree.
// It's initialized with the full column range.
X_NODE xtree;
Y_NODE() : xtree(1, C_max_dim) {}
~Y_NODE() {
delete left;
delete right;
}
};
// --- Core Functions Matching the Accepted Solution ---
// Update function for the inner/column tree (X_NODE)
void update_y(X_NODE* node, int q, ll 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) {
// Optimization: If no child exists, create a single leaf node directly.
// This avoids creating the full path and is the key memory saver.
*child_ptr = new X_NODE(q, q);
(*child_ptr)->value = k;
} else if ((*child_ptr)->s <= q && q <= (*child_ptr)->e) {
// Child exists and its range covers the target point, so recurse.
update_y(*child_ptr, q, k);
} else {
// Tricky case: Child exists but doesn't cover the point.
// We need to create a new parent to hold both the old child and the new point.
int new_s = s, new_e = e;
int 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);
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);
}
// After recursion, update this node's value
ll left_val = node->left ? node->left->value : 0;
ll right_val = node->right ? node->right->value : 0;
node->value = merge(left_val, right_val);
}
// Query function for the inner/column tree (X_NODE)
ll query_y(X_NODE* node, int s, int e) {
if (node == nullptr || node->s > e || node->e < s) {
return 0;
}
if (s <= node->s && node->e <= e) {
return node->value;
}
return merge(query_y(node->left, s, e), query_y(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, ll k) {
if (s == e) {
// Reached the leaf row, update its column tree
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();
update_x(node->left, s, m, p, q, k);
} else {
if (node->right == nullptr) node->right = new Y_NODE();
update_x(node->right, m + 1, e, p, q, k);
}
// Bottom-up update: query children to update this node's column tree
ll left_val = node->left ? query_y(&node->left->xtree, q, q) : 0;
ll right_val = node->right ? query_y(&node->right->xtree, q, q) : 0;
update_y(&node->xtree, q, merge(left_val, right_val));
}
// Query function for the outer/row tree (Y_NODE)
ll 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 0;
}
if (p <= s && e <= u) {
// This row range is fully contained, query its column tree
return query_y(&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));
}
// --- Interface Functions ---
void init(int R, int C) {
R_min_dim = 1;
C_min_dim = 1;
R_max_dim = R;
C_max_dim = C;
delete root; // Delete old tree if it exists from a previous test case
root = new Y_NODE();
}
void update(int P, int Q, long long K) {
update_x(root, R_min_dim, R_max_dim, P + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
return query_x(root, R_min_dim, R_max_dim, P + 1, Q + 1, U + 1, V + 1);
}
