#include "game.h"
#include <algorithm>
using namespace std;
typedef long long ll;
// 正確的 GCD 處理，確保包含 0 的情況
ll gcd(ll a, ll b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
struct nodey {
nodey *l, *r;
ll val;
nodey() : l(nullptr), r(nullptr), val(0) {}
};
struct nodex {
nodex *l, *r;
nodey *nd;
nodex() : l(nullptr), r(nullptr), nd(nullptr) {}
};
nodex *rt = nullptr;
int maxR, maxC;
// 更新內層 Y 軸
void updy(nodey *&idx, int q, ll val, int ql, int qr) {
if (!idx) idx = new nodey();
if (ql == qr) {
idx->val = val;
return;
}
int mid = ql + (qr - ql) / 2;
if (q <= mid) updy(idx->l, q, val, ql, mid);
else updy(idx->r, q, val, mid + 1, qr);
ll v1 = idx->l ? idx->l->val : 0;
ll v2 = idx->r ? idx->r->val : 0;
idx->val = gcd(v1, v2);
}
// 專門用於獲取特定點的 GCD 值
ll get_valy(nodey *idx, int q, int ql, int qr) {
if (!idx) return 0;
if (ql == qr) return idx->val;
int mid = ql + (qr - ql) / 2;
if (q <= mid) return get_valy(idx->l, q, ql, mid);
else return get_valy(idx->r, q, mid + 1, qr);
}
void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
if (!idx) idx = new nodex();
if (ql == qr) {
// 如果是 X 軸的葉子（代表某一行），直接更新該行的 Y 軸樹
updy(idx->nd, q, val, 0, maxC - 1);
return;
}
int mid = ql + (qr - ql) / 2;
if (p <= mid) updx(idx->l, p, q, val, ql, mid);
else updx(idx->r, p, q, val, mid + 1, qr);
// 非葉子節點：當前位置的 GCD = 左子樹位置與右子樹位置的 GCD
ll v1 = idx->l ? get_valy(idx->l->nd, q, 0, maxC - 1) : 0;
ll v2 = idx->r ? get_valy(idx->r->nd, q, 0, maxC - 1) : 0;
updy(idx->nd, q, gcd(v1, v2), 0, maxC - 1);
}
ll qryy(nodey *idx, int u, int v, int ql, int qr) {
if (!idx || ql > v || qr < u) return 0;
if (u <= ql && qr <= v) return idx->val;
int mid = ql + (qr - ql) / 2;
return gcd(qryy(idx->l, u, v, ql, mid), qryy(idx->r, u, v, mid + 1, qr));
}
ll qryx(nodex *idx, int p, int q, int u, int v, int ql, int qr) {
if (!idx || ql > q || qr < p) return 0;
if (p <= ql && qr <= q) return qryy(idx->nd, u, v, 0, maxC - 1);
int mid = ql + (qr - ql) / 2;
return gcd(qryx(idx->l, p, q, u, v, ql, mid), qryx(idx->r, p, q, u, v, mid + 1, qr));
}
void init(int R, int C) {
maxR = R; maxC = C;
rt = nullptr; // 重置樹
}
void update(int P, int Q, ll K) {
updx(rt, P, Q, K, 0, maxR - 1);
}
ll calculate(int P, int Q, int U, int V) {
// 修正點 1: 確保查詢區間 P <= U 且 Q <= V
int r1 = min(P, U), r2 = max(P, U);
int c1 = min(Q, V), c2 = max(Q, V);
// 修正點 2: 傳遞正確的軸範圍給 qryx
// qryx(root, X_start, X_end, Y_start, Y_end, root_X_L, root_X_R)
return qryx(rt, r1, r2, c1, c2, 0, maxR - 1);
}
