#include "game.h"
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
// --- Helper: GCD ---
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != 0 && Y != 0) {
if (X > Y) X %= Y;
else Y %= X;
}
return X + Y;
}
// --- Treap (Y-Dimension) ---
// Standard Treap supporting point update and range GCD query.
struct Treap {
int key; // Column index
int prio; // Random priority
long long val; // Value at this column
long long gcd_val; // GCD of the subtree
Treap *l, *r;
Treap(int k, long long v) : key(k), prio(rand()), val(v), gcd_val(v), l(NULL), r(NULL) {}
};
// Update the gcd_val of a node based on children
void update_gcd(Treap *t) {
if (!t) return;
t->gcd_val = t->val;
if (t->l) t->gcd_val = gcd2(t->gcd_val, t->l->gcd_val);
if (t->r) t->gcd_val = gcd2(t->gcd_val, t->r->gcd_val);
}
// Split treap 't' by key 'k' into 'l' (keys <= k) and 'r' (keys > k)
void split(Treap *t, int k, Treap *&l, Treap *&r) {
if (!t) {
l = r = NULL;
} else if (t->key <= k) {
split(t->r, k, t->r, r);
l = t;
} else {
split(t->l, k, l, t->l);
r = t;
}
update_gcd(t);
}
// Merge treaps 'l' and 'r'
void merge(Treap *&t, Treap *l, Treap *r) {
if (!l || !r) {
t = (l ? l : r);
} else if (l->prio > r->prio) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
update_gcd(t);
}
// Insert or Update a value in the Treap
// If key exists, update value. If not, insert.
void treap_update(Treap *&t, int key, long long val) {
Treap *t1, *t2, *t3;
// Split into < key, == key, > key
split(t, key, t2, t3); // t2 has <= key
split(t2, key - 1, t1, t2); // t1 has < key, t2 has == key
// t2 is now the node with 'key' if it exists, or NULL
if (t2) {
t2->val = val;
update_gcd(t2);
} else {
t2 = new Treap(key, val);
}
// Merge back: t1 + t2 + t3
merge(t2, t1, t2);
merge(t, t2, t3);
}
// Query GCD in range [ql, qr] on the Treap
long long treap_query(Treap *t, int ql, int qr) {
Treap *t1, *t2, *t3;
// Split to isolate the range [ql, qr]
split(t, qr, t2, t3); // t2 <= qr, t3 > qr
split(t2, ql - 1, t1, t2); // t1 < ql, t2 is range [ql, qr]
long long res = (t2 ? t2->gcd_val : 0);
// Merge back to restore structure
merge(t2, t1, t2);
merge(t, t2, t3);
return res;
}
// Fast point query helper for calculating internal X-nodes
// (Avoids split/merge overhead)
long long treap_get_val(Treap *t, int key) {
while (t) {
if (key == t->key) return t->val;
if (key < t->key) t = t->l;
else t = t->r;
}
return 0;
}
// --- Segment Tree (X-Dimension) ---
// Dynamic Segment Tree on rows.
struct NodeX {
NodeX *l, *r;
Treap *rootY; // The Y-dimension structure for this row range
NodeX() : l(NULL), r(NULL), rootY(NULL) {}
};
NodeX *rootX = NULL;
int R_global, C_global;
// Update the 2D structure
// node: current X-node
// nl, nr: current row range
// r, c: target coordinate
// val: new value
void updateX(NodeX *&node, int nl, int nr, int r, int c, long long val) {
if (!node) node = new NodeX();
// If we are at the exact row (leaf of X-tree)
if (nl == nr) {
treap_update(node->rootY, c, val);
return;
}
int mid = nl + (nr - nl) / 2;
if (r <= mid) updateX(node->l, nl, mid, r, c, val);
else updateX(node->r, mid + 1, nr, r, c, val);
// Update logic for internal nodes:
// The value at (row_range, c) in the X-tree should be:
// gcd( value at (left_child, c), value at (right_child, c) )
long long v1 = (node->l) ? treap_get_val(node->l->rootY, c) : 0;
long long v2 = (node->r) ? treap_get_val(node->r->rootY, c) : 0;
treap_update(node->rootY, c, gcd2(v1, v2));
}
// Query the 2D structure
long long queryX(NodeX *node, int nl, int nr, int r1, int r2, int c1, int c2) {
if (!node || nl > r2 || nr < r1) return 0;
// If the X-range is fully within the query range
if (nl >= r1 && nr <= r2) {
return treap_query(node->rootY, c1, c2);
}
int mid = nl + (nr - nl) / 2;
return gcd2(queryX(node->l, nl, mid, r1, r2, c1, c2),
queryX(node->r, mid + 1, nr, r1, r2, c1, c2));
}
// --- Interface ---
void init(int R, int C) {
R_global = R;
C_global = C;
srand(2013); // Seed for Treap priorities
rootX = new NodeX();
}
void update(int P, int Q, long long K) {
updateX(rootX, 0, R_global - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(rootX, 0, R_global - 1, P, U, Q, V);
}
