#include "game.h"
#include <algorithm>
using namespace std;
typedef long long ll;
// 標準 GCD 函數
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 軸線段樹
// mode = 0: 直接更新 leaf 的值 (外層是 leaf)
// mode = 1: 取左右子樹的 GCD (外層是非 leaf)
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);
}
// 獲取內層樹特定位置的值，用於外層非葉子節點的合併
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);
}
// 更新外層 X 軸線段樹
void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
if (!idx) idx = new nodex();
if (ql == qr) {
// 外層葉子：直接更新內層
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);
// 非葉子節點：內層位置 Q 的值 = gcd(左子樹位置 Q, 右子樹位置 Q)
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);
}
// 查詢內層 Y 軸
ll qryy(nodey *idx, int u, int v, int ql, int qr) {
if (!idx || u > qr || v < ql) 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));
}
// 查詢外層 X 軸
ll qryx(nodex *idx, int p, int q, int u, int v, int ql, int qr) {
if (!idx || p > qr || q < ql) 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) {
return qryx(rt, P, Q, U, V, 0, maxR - 1);
}
