#include "game.h"
#include <algorithm> // For std::swap and __gcd
#define ll long long
// MAXIMIZED MEMORY LIMITS (Targeting ~248MiB total)
const int NODE_Y_MAX = 14800000; // ~236.8 MB
const int NODE_X_MAX = 1000000; // ~11.4 MB
const int NMAX = 1e9;
// Use built-in GCD for speed (GCC builtin), or fallback to manual if needed.
// __gcd is available in <algorithm> in most competitive programming environments.
long long gcd_algo(long long a, long long b) {
return std::__gcd(a, b);
}
int n, m, root_x;
int nodes_y = 0;
int nodes_x = 0;
// Packed structures to ensure no padding bytes are wasted
struct NodeY {
ll gcd;
int left, right;
} aint_y[NODE_Y_MAX + 2];
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; // Prevent SEGFAULT if limit reached
return ++nodes_x;
}
int create_node_y() {
if (nodes_y >= NODE_Y_MAX) return 0; // Prevent SEGFAULT if limit reached
return ++nodes_y;
}
void updateY(int& node, int left, int right, int pos, ll value) {
if(!node) {
node = create_node_y();
if(!node) return; // Safety exit if OOM
}
if(left == right) {
aint_y[node].gcd = value;
return;
}
int mid = (left + right) >> 1;
if(pos <= mid) {
updateY(aint_y[node].left, left, mid, pos, value);
}
else {
updateY(aint_y[node].right, mid + 1, right, pos, value);
}
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 = gcd_algo(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 gcd_algo(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) {
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);
}
// --- OPTIMIZATION: Check before update ---
// Calculate what the new GCD *would* be for this column
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 = gcd_algo(val_left, val_right);
// Get the current existing GCD in the tree
ll current_gcd = queryY(aint_x[node].root_y, 1, m, pos_y, pos_y);
// Only commit the update to the Y-tree if the value effectively changes.
// This saves massive amounts of memory on the path up the X-tree.
if (new_gcd != current_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 gcd_algo(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;
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);
}
