#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); }