#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// We’ll use std::gcd on long long
// (C++17 <numeric> is included via <bits/stdc++.h>)
struct NodeY {
long long val = 0;
NodeY *l = nullptr, *r = nullptr;
};
struct NodeX {
NodeX *l = nullptr, *r = nullptr;
NodeY *treeY = nullptr;
};
int n, m;
NodeX* root = nullptr;
// Merge two Y‑trees over [ly, ry], return a newly built tree
NodeY* mergeY(NodeY* A, NodeY* B, int ly, int ry) {
if (!A && !B) return nullptr;
NodeY* node = new NodeY();
if (ly == ry) {
long long va = A ? A->val : 0;
long long vb = B ? B->val : 0;
node->val = std::gcd(va, vb);
return node;
}
int my = (ly + ry) >> 1;
node->l = mergeY(A ? A->l : nullptr, B ? B->l : nullptr, ly, my);
node->r = mergeY(A ? A->r : nullptr, B ? B->r : nullptr, my+1, ry);
long long vl = node->l ? node->l->val : 0;
long long vr = node->r ? node->r->val : 0;
node->val = std::gcd(vl, vr);
return node;
}
// Point‐set update on Y‑tree at fixed X‑node
void updateY(NodeY*& node, int ly, int ry, int y, long long v) {
if (!node) node = new NodeY();
if (ly == ry) {
node->val = v;
return;
}
int my = (ly + ry) >> 1;
if (y <= my) updateY(node->l, ly, my, y, v);
else updateY(node->r, my+1, ry, y, v);
long long vl = node->l ? node->l->val : 0;
long long vr = node->r ? node->r->val : 0;
node->val = std::gcd(vl, vr);
}
// Update X‑tree: set a[x][y]=v
void updateX(NodeX*& node, int lx, int rx, int x, int y, long long v) {
if (!node) node = new NodeX();
if (lx == rx) {
// leaf in X: just update its Y‑tree
updateY(node->treeY, 0, m-1, y, v);
return;
}
int mx = (lx + rx) >> 1;
if (x <= mx) updateX(node->l, lx, mx, x, y, v);
else updateX(node->r, mx+1, rx, x, y, v);
// after children are updated, merge their Y‑trees
node->treeY = mergeY(
node->l ? node->l->treeY : nullptr,
node->r ? node->r->treeY : nullptr,
0, m-1
);
}
// GCD query on a single Y‑tree
long long queryY(NodeY* node, int ly, int ry, int y1, int y2) {
if (!node || ry < y1 || ly > y2) return 0;
if (y1 <= ly && ry <= y2) return node->val;
int my = (ly + ry) >> 1;
return std::gcd(
queryY(node->l, ly, my, y1, y2),
queryY(node->r, my+1, ry, y1, y2)
);
}
// Submatrix GCD query on [x1,x2]×[y1,y2]
long long queryX(NodeX* node, int lx, int rx,
int x1, int x2, int y1, int y2) {
if (!node || rx < x1 || lx > x2) return 0;
if (x1 <= lx && rx <= x2) {
// fully covered in X → query its Y‑tree
return queryY(node->treeY, 0, m-1, y1, y2);
}
int mx = (lx + rx) >> 1;
return std::gcd(
queryX(node->l, lx, mx, x1, x2, y1, y2),
queryX(node->r, mx+1, rx, x1, x2, y1, y2)
);
}
// game.h interface
void init(int R, int C) {
n = R;
m = C;
root = nullptr;
}
void update(int P, int Q, long long K) {
// set a[P][Q] = K
updateX(root, 0, n-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
// query GCD on [P..U]×[Q..V]
return queryX(root, 0, n-1, P, U, Q, V);
}
