#include "game.h"
// MEMORY CALCULATION:
// NodeY: 16 bytes * 13,000,000 ~= 208 MB
// NodeX: 12 bytes * 700,000 ~= 8.4 MB
// Total Static: ~216.4 MB (Leaves ~33 MB for stack/overhead within 250 MB)
const int NODE_Y_MAX = 13000000;
const int NODE_X_MAX = 700000;
const int NMAX = 1e9;
#define ll long long
long long gcd2(long long X, long long Y) {
long long tmp;
while (Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int n, m, root_x;
int nodes_y = 0;
int nodes_x = 0;
struct NodeY {
ll gcd;
int left, right;
} aint_y[NODE_Y_MAX + 2]; // +2 for safety
struct NodeX {
int root_y;
int left, right;
} aint_x[NODE_X_MAX + 2];
int create_node_x() {
if (nodes_x >= NODE_X_MAX) return 0; // Safety check
return ++nodes_x;
}
int create_node_y() {
if (nodes_y >= NODE_Y_MAX) return 0; // Safety check
return ++nodes_y;
}
void updateY(int& node, int left, int right, int pos, ll value) {
if(!node) {
node = create_node_y();
if (!node) return; // Out of memory
}
if(left == right) {
aint_y[node].gcd = value;
return;
}
int mid = (left + right) >> 1; // Bitwise shift is slightly faster
if(pos <= mid) {
updateY(aint_y[node].left, left, mid, pos, value);
}
else {
updateY(aint_y[node].right, mid + 1, right, pos, value);
}
// Recalculate current node's GCD from children
ll left_gcd = aint_y[node].left ? aint_y[aint_y[node].left].gcd : 0;
ll right_gcd = aint_y[node].right ? aint_y[aint_y[node].right].gcd : 0;
aint_y[node].gcd = gcd2(left_gcd, right_gcd);
}
ll queryY(int node, int left, int right, int qleft, int qright) {
if(!node || left > qright || right < qleft) {
return 0;
}
if(left >= qleft && right <= qright) {
return aint_y[node].gcd;
}
int mid = (left + right) >> 1;
return gcd2(queryY(aint_y[node].left, left, mid, qleft, qright),
queryY(aint_y[node].right, mid + 1, right, qleft, qright));
}
void updateX(int& node, int left_x, int right_x, int pos_x, int pos_y, ll value) {
if(!node) {
node = create_node_x();
if (!node) return;
}
if(left_x == right_x) {
// Leaf in X-tree: Just update the Y-tree
updateY(aint_x[node].root_y, 1, m, pos_y, value);
return;
}
int mid_x = (left_x + right_x) >> 1;
if(pos_x <= mid_x) {
updateX(aint_x[node].left, left_x, mid_x, pos_x, pos_y, value);
}
else {
updateX(aint_x[node].right, mid_x + 1, right_x, pos_x, pos_y, value);
}
// --- CRITICAL MEMORY OPTIMIZATION ---
// 1. Calculate what the new GCD for this (pos_y) SHOULD be based on children
ll val_left = 0, val_right = 0;
if (aint_x[node].left)
val_left = queryY(aint_x[aint_x[node].left].root_y, 1, m, pos_y, pos_y);
if (aint_x[node].right)
val_right = queryY(aint_x[aint_x[node].right].root_y, 1, m, pos_y, pos_y);
ll new_gcd = gcd2(val_left, val_right);
// 2. Check what is CURRENTLY stored at this (pos_y) in this node's Y-tree
ll current_stored_gcd = queryY(aint_x[node].root_y, 1, m, pos_y, pos_y);
// 3. Only update if the value actually changes.
// This prevents creating a path of ~30 nodes in the Y-tree for every X-update
// when the GCD remains stable (common in sparse grids).
if (new_gcd != current_stored_gcd) {
updateY(aint_x[node].root_y, 1, m, pos_y, new_gcd);
}
}
ll queryX(int node, int left_x, int right_x, int qleft_x, int qleft_y, int qright_x, int qright_y) {
if(!node || left_x > qright_x || right_x < qleft_x) {
return 0;
}
if(left_x >= qleft_x && right_x <= qright_x) {
return queryY(aint_x[node].root_y, 1, m, qleft_y, qright_y);
}
int mid_x = (left_x + right_x) >> 1;
return gcd2(queryX(aint_x[node].left, left_x, mid_x, qleft_x, qleft_y, qright_x, qright_y),
queryX(aint_x[node].right, mid_x + 1, right_x, qleft_x, qleft_y, qright_x, qright_y));
}
void init(int R, int C) {
n = R; m = C;
nodes_x = 0; nodes_y = 0;
// Clear roots if necessary for multiple test cases,
// but IOI tasks usually run once per execution.
root_x = create_node_x();
}
void update(int P, int Q, long long K) {
updateX(root_x, 1, n, P + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(root_x, 1, n, P + 1, Q + 1, U + 1, V + 1);
}
