#include "game.h"
#include <algorithm>
using namespace std;
typedef long long ll;
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)
// ---------------------------------------------------------
// 節點大小嚴格控制在 16 Bytes
struct NodeY {
int l; // 若是內部節點：左子樹索引；若是葉子：儲存列座標 (Key)
int r; // 若是內部節點：右子樹索引；若是葉子：標記為 -1
ll val; // GCD 數值
};
// 記憶體池：開 1300 萬個節點 (約 200 MB)
// Subtask 5 極限約需 1.2e7 節點
const int MAX_NODES_Y = 13000000;
NodeY treeY[MAX_NODES_Y];
int ptrY = 1;
int new_nodeY() {
return ptrY++;
}
// 內層更新：支援葉節點優化
void updateY(int &node, int l, int r, int pos, ll k) {
if (!node) {
// 情況 1: 空節點，直接建立葉子
node = new_nodeY();
treeY[node].l = pos; // 借用 l 存座標
treeY[node].r = -1; // 標記為葉子
treeY[node].val = k;
return;
}
// 情況 2: 當前是葉子節點
if (treeY[node].r == -1) {
// 如果座標相同，直接更新數值
if (treeY[node].l == pos) {
treeY[node].val = k;
return;
}
// 座標不同（衝突），必須分裂成內部節點
int old_pos = treeY[node].l;
ll old_val = treeY[node].val;
// 轉為內部節點 (重置左右子樹)
treeY[node].l = 0;
treeY[node].r = 0;
treeY[node].val = gcd2(old_val, k); // 先預存 GCD
// 遞迴插入舊的值與新的值
// 注意：這裡直接呼叫遞迴，讓系統自動分配到正確的子層
updateY(node, l, r, old_pos, old_val);
updateY(node, l, r, pos, k);
return;
}
// 情況 3: 內部節點，標準線段樹遞迴
int mid = l + (r - l) / 2;
if (pos <= mid) updateY(treeY[node].l, l, mid, pos, k);
else updateY(treeY[node].r, mid + 1, r, pos, k);
// Pull: 更新 GCD
ll val_l = treeY[node].l ? treeY[treeY[node].l].val : 0;
ll val_r = treeY[node].r ? treeY[treeY[node].r].val : 0;
treeY[node].val = gcd2(val_l, val_r);
}
// 內層查詢
ll queryY(int node, int l, int r, int ql, int qr) {
if (!node || l > qr || r < ql) return 0;
// 如果是葉子節點，檢查座標是否在範圍內
if (treeY[node].r == -1) {
int key = treeY[node].l;
if (key >= ql && key <= qr) return treeY[node].val;
return 0;
}
// 標準區間查詢
if (ql <= l && r <= qr) return treeY[node].val;
int mid = l + (r - l) / 2;
return gcd2(queryY(treeY[node].l, l, mid, ql, qr),
queryY(treeY[node].r, mid + 1, r, ql, qr));
}
// ---------------------------------------------------------
// 外層線段樹 (X軸 - Rows)
// ---------------------------------------------------------
struct NodeX {
int l, r;
int rootY; // 內層樹根
};
// 外層節點數較少 (22000 * 30 ~ 660,000)
const int MAX_NODES_X = 700000;
NodeX treeX[MAX_NODES_X];
int ptrX = 1;
int rootX = 0;
int R_MAX, C_MAX;
// 輔助：從內層樹取得單點的值 (用於外層合併)
ll get_val_at(int inner_root, int col) {
// 利用 queryY 查詢單點 [col, col]
return queryY(inner_root, 0, C_MAX - 1, col, col);
}
void updateX(int &node, int l, int r, int P, int Q, ll K) {
if (!node) node = ptrX++;
// 1. 葉子行 (Row P)
if (l == r) {
updateY(treeX[node].rootY, 0, C_MAX - 1, Q, K);
return;
}
int mid = l + (r - l) / 2;
if (P <= mid) updateX(treeX[node].l, l, mid, P, Q, K);
else updateX(treeX[node].r, mid + 1, r, P, Q, K);
// 2. 內部行：計算新的 GCD 並更新到內層樹
// 這裡我們需要知道左子樹和右子樹在 (P, Q) 處的值
// 注意：只更新列 Q，因為只有這個位置變了
ll val_l = treeX[node].l ? get_val_at(treeX[treeX[node].l].rootY, Q) : 0;
ll val_r = treeX[node].r ? get_val_at(treeX[treeX[node].r].rootY, Q) : 0;
updateY(treeX[node].rootY, 0, C_MAX - 1, Q, gcd2(val_l, val_r));
}
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) {
return queryY(treeX[node].rootY, 0, C_MAX - 1, Q, V);
}
int mid = l + (r - l) / 2;
return gcd2(queryX(treeX[node].l, l, mid, P, Q, U, V),
queryX(treeX[node].r, 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);
}
