#include "game.h"
#include <algorithm>
using namespace std;
typedef long long ll;
// 題目提供的 GCD 函數
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
// ---------------------------------------------------------
// 內層線段樹 (Y軸 - 列 Columns)
// ---------------------------------------------------------
struct NodeY {
int left_child;
int right_child;
ll val; // 儲存區間 GCD
};
// 記憶體池：內層節點數量龐大，需要開大一點
const int MAX_NODES_Y = 250000*50;
NodeY treeY[MAX_NODES_Y];
int ptrY = 1; // 0 保留給空節點 (NULL)
int get_nodeY() {
return ptrY++;
}
// 內層：更新位置 pos 的值為 k
void updateY(int &node, int l, int r, int pos, ll k) {
if (!node) node = get_nodeY();
if (l == r) {
treeY[node].val = k;
return;
}
int mid = l + (r - l) / 2;
if (pos <= mid) updateY(treeY[node].left_child, l, mid, pos, k);
else updateY(treeY[node].right_child, mid + 1, r, pos, k);
treeY[node].val = gcd2(treeY[treeY[node].left_child].val,
treeY[treeY[node].right_child].val);
}
// 內層：查詢區間 [ql, qr] 的 GCD
ll queryY(int node, int l, int r, int ql, int qr) {
if (!node || l > qr || r < ql) return 0;
if (ql <= l && r <= qr) return treeY[node].val;
int mid = l + (r - l) / 2;
return gcd2(queryY(treeY[node].left_child, l, mid, ql, qr),
queryY(treeY[node].right_child, mid + 1, r, ql, qr));
}
// ---------------------------------------------------------
// 外層線段樹 (X軸 - 行 Rows)
// ---------------------------------------------------------
struct NodeX {
int left_child;
int right_child;
int rootY; // 指向內層線段樹的根
};
// 外層節點數量較少 (N_U * log R)
const int MAX_NODES_X = 250000*50;
NodeX treeX[MAX_NODES_X];
int ptrX = 1;
int rootX = 0;
int R_MAX, C_MAX;
// 輔助：從某個內層樹查詢單點 val (用來合併外層節點)
ll get_val_at_col(int inner_root, int col) {
return queryY(inner_root, 0, C_MAX - 1, col, col);
}
// 外層：更新 (P, Q) 為 K
void updateX(int &node, int l, int r, int P, int Q, ll K) {
if (!node) {
node = ptrX++;
treeX[node].rootY = 0; // 初始內層樹為空
}
// 1. 如果是葉子節點 (特定的行 P)
if (l == r) {
// 直接在內層樹更新列 Q
updateY(treeX[node].rootY, 0, C_MAX - 1, Q, K);
return;
}
int mid = l + (r - l) / 2;
if (P <= mid) updateX(treeX[node].left_child, l, mid, P, Q, K);
else updateX(treeX[node].right_child, mid + 1, r, P, Q, K);
// 2. 如果是內部節點 (行區間)
// 我們需要在這個節點的「內層樹」中，更新列 Q 的值。
// 這個值應該是：GCD(左子樹在Q的值, 右子樹在Q的值)
ll val_left = 0, val_right = 0;
if (treeX[node].left_child)
val_left = get_val_at_col(treeX[treeX[node].left_child].rootY, Q);
if (treeX[node].right_child)
val_right = get_val_at_col(treeX[treeX[node].right_child].rootY, Q);
ll new_gcd = gcd2(val_left, val_right);
// 更新當前外層節點的內層樹
updateY(treeX[node].rootY, 0, C_MAX - 1, Q, new_gcd);
}
// 外層：查詢矩形
ll queryX(int node, int l, int r, int P, int Q, int U, int V) {
if (!node || l > U || r < P) return 0;
// 如果行範圍完全被包含
if (P <= l && r <= U) {
// 直接查詢該節點的內層樹 (列範圍 Q~V)
return queryY(treeX[node].rootY, 0, C_MAX - 1, Q, V);
}
int mid = l + (r - l) / 2;
return gcd2(queryX(treeX[node].left_child, l, mid, P, Q, U, V),
queryX(treeX[node].right_child, mid + 1, r, P, Q, U, V));
}
// ---------------------------------------------------------
// 介面實作
// ---------------------------------------------------------
void init(int R, int C) {
R_MAX = R;
C_MAX = C;
ptrX = 1;
ptrY = 1;
rootX = 0;
}
void update(int P, int Q, long long K) {
updateX(rootX, 0, R_MAX - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(rootX, 0, R_MAX - 1, P, Q, U, V);
}
