#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); }