#include "game.h"
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Standard GCD function
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != 0 && Y != 0) {
if (X > Y) X %= Y;
else Y %= X;
}
return X + Y;
}
// Inner Segment Tree Node (Y-dimension)
struct NodeY {
int left = 0;
int right = 0;
long long val = 0;
};
// Outer Segment Tree Node (X-dimension)
struct NodeX {
int left = 0;
int right = 0;
int rootY = 0; // Root of the inner tree for this X-range
};
// Memory pools
// We reserve enough space. N * log(R) * log(C) roughly.
// Max nodes estimate: 22000 ops * 30 * 30 ~ 20M nodes.
const int MAX_NODES = 25000000;
// We use global vectors to act as our "heap"
// Index 0 is reserved as "null"
vector<NodeY> treeY;
vector<NodeX> treeX;
int rootX = 0;
int ROWS, COLS;
// --- Inner Tree (Y-axis) Operations ---
// Update the inner tree at position 'pos' with 'val'
// node_idx: current node in Y-tree
// l, r: current range coverage of this node
void updateY(int &node_idx, int l, int r, int pos, long long val) {
if (!node_idx) {
node_idx = treeY.size();
treeY.push_back({0, 0, 0});
}
if (l == r) {
treeY[node_idx].val = val;
return;
}
int mid = l + (r - l) / 2;
if (pos <= mid) {
updateY(treeY[node_idx].left, l, mid, pos, val);
} else {
updateY(treeY[node_idx].right, mid + 1, r, pos, val);
}
long long valL = treeY[node_idx].left ? treeY[treeY[node_idx].left].val : 0;
long long valR = treeY[node_idx].right ? treeY[treeY[node_idx].right].val : 0;
treeY[node_idx].val = gcd2(valL, valR);
}
// Query the inner tree
long long queryY(int node_idx, int l, int r, int ql, int qr) {
if (!node_idx || l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return treeY[node_idx].val;
int mid = l + (r - l) / 2;
return gcd2(queryY(treeY[node_idx].left, l, mid, ql, qr),
queryY(treeY[node_idx].right, mid + 1, r, ql, qr));
}
// --- Outer Tree (X-axis) Operations ---
// Helper to get value at a specific column 'posK' from an existing Y-tree
long long get_val_from_Y(int nodeX_idx, int posK) {
if (!nodeX_idx) return 0;
// We strictly query a single point (posK, posK) in the Y-tree
return queryY(treeX[nodeX_idx].rootY, 0, COLS - 1, posK, posK);
}
// Update the outer tree
// r, c: target coordinates
// val: new value
void updateX(int &node_idx, int l, int r, int target_r, int target_c, long long val) {
if (!node_idx) {
node_idx = treeX.size();
treeX.push_back({0, 0, 0});
}
// Whether leaf or internal, we must update the Y-tree associated with this X-node.
if (l == r) {
// Leaf in X-tree: represents exactly one row.
// Just update the Y-tree normally.
updateY(treeX[node_idx].rootY, 0, COLS - 1, target_c, val);
} else {
int mid = l + (r - l) / 2;
if (target_r <= mid) {
updateX(treeX[node_idx].left, l, mid, target_r, target_c, val);
} else {
updateX(treeX[node_idx].right, mid + 1, r, target_r, target_c, val);
}
// Internal node logic:
// The value at (target_r, target_c) has changed.
// This X-node represents a range of rows. The Y-tree at this node
// must store gcd( lower_half_row_val, upper_half_row_val ) at column target_c.
long long v1 = get_val_from_Y(treeX[node_idx].left, target_c);
long long v2 = get_val_from_Y(treeX[node_idx].right, target_c);
long long new_gcd = gcd2(v1, v2);
updateY(treeX[node_idx].rootY, 0, COLS - 1, target_c, new_gcd);
}
}
long long queryX(int node_idx, int l, int r, int r1, int r2, int c1, int c2) {
if (!node_idx || l > r2 || r < r1) return 0;
if (l >= r1 && r <= r2) {
// Entire X-range is within query.
// Query the Y-tree for the column range.
return queryY(treeX[node_idx].rootY, 0, COLS - 1, c1, c2);
}
int mid = l + (r - l) / 2;
return gcd2(queryX(treeX[node_idx].left, l, mid, r1, r2, c1, c2),
queryX(treeX[node_idx].right, mid + 1, r, r1, r2, c1, c2));
}
// --- Interface Functions ---
void init(int R, int C) {
ROWS = R;
COLS = C;
// Reserve memory to prevent reallocations invalidating references
// (though indices are safe, resizing is slow)
treeY.reserve(MAX_NODES);
treeX.reserve(200000); // Outer tree has much fewer nodes
// Push dummy 0-th node
treeY.push_back({0, 0, 0});
treeX.push_back({0, 0, 0});
}
void update(int P, int Q, long long K) {
updateX(rootX, 0, ROWS - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(rootX, 0, ROWS - 1, P, U, Q, V);
}
