#include "game.h"
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
// Helper: GCD of two numbers (provided by problem statement)
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
// ---------------------------------------------------------
// INNER DATA STRUCTURE: TREAP (Handles Columns)
// ---------------------------------------------------------
struct TreapNode {
int left_idx; // Index in pool
int right_idx; // Index in pool
int key; // Column index
int prio; // Random priority
ll val; // Value at this specific column
ll gcd_val; // GCD of the whole subtree
};
// Memory Pool for Treap
const int MAX_TREAP_NODES = 6000000; // Sufficient for Nu * log(R) * const
TreapNode treap_pool[MAX_TREAP_NODES];
int treap_ptr = 1; // 0 is reserved for NULL
// Helper to get GCD of a node (handles 0/NULL index gracefully)
ll get_treap_gcd(int t_idx) {
return (t_idx == 0) ? 0 : treap_pool[t_idx].gcd_val;
}
// Update the gcd_val of a node based on children
void pull_treap(int t_idx) {
if (t_idx == 0) return;
ll l_gcd = get_treap_gcd(treap_pool[t_idx].left_idx);
ll r_gcd = get_treap_gcd(treap_pool[t_idx].right_idx);
treap_pool[t_idx].gcd_val = gcd2(treap_pool[t_idx].val, gcd2(l_gcd, r_gcd));
}
// Create new node
int new_treap_node(int key, ll val) {
int idx = treap_ptr++;
treap_pool[idx].left_idx = 0;
treap_pool[idx].right_idx = 0;
treap_pool[idx].key = key;
treap_pool[idx].prio = rand();
treap_pool[idx].val = val;
treap_pool[idx].gcd_val = val;
return idx;
}
// Split Treap by key
void split(int t, int key, int &l, int &r) {
if (t == 0) {
l = r = 0;
} else if (treap_pool[t].key <= key) {
split(treap_pool[t].right_idx, key, treap_pool[t].right_idx, r);
l = t;
} else {
split(treap_pool[t].left_idx, key, l, treap_pool[t].left_idx);
r = t;
}
pull_treap(t);
}
// Merge two Treaps
void merge(int &t, int l, int r) {
if (l == 0 || r == 0) {
t = (l != 0) ? l : r;
} else if (treap_pool[l].prio > treap_pool[r].prio) {
merge(treap_pool[l].right_idx, treap_pool[l].right_idx, r);
t = l;
} else {
merge(treap_pool[r].left_idx, l, treap_pool[r].left_idx);
t = r;
}
pull_treap(t);
}
// Update point (col) in Treap with value K
void treap_update(int &root, int col, ll K) {
int t1 = 0, t2 = 0, t3 = 0;
split(root, col, t1, t2); // t1: <= col
split(t1, col - 1, t1, t3); // t1: < col, t3: == col
// t3 is the node with 'col' if it exists.
// We replace it or create a new one.
// Note: We don't reuse the memory of t3 to keep it simple,
// or we can reuse t3 if it exists. Let's make a new node or update.
if (t3 != 0) {
treap_pool[t3].val = K;
treap_pool[t3].gcd_val = K;
// Re-pulling isn't strictly needed as it has no children after split,
// but let's be safe.
pull_treap(t3);
} else {
t3 = new_treap_node(col, K);
}
merge(t1, t1, t3);
merge(root, t1, t2);
}
// Query range [L, R] in Treap
ll treap_query(int root, int L, int R) {
int t1 = 0, t2 = 0, t3 = 0;
// Split into: < L, [L, R], > R
split(root, R, t1, t2); // t1 <= R, t2 > R
split(t1, L - 1, t1, t3); // t1 < L, t3 is range [L, R]
ll res = get_treap_gcd(t3);
// Merge back to restore structure
merge(t1, t1, t3);
merge(root, t1, t2);
return res;
}
// ---------------------------------------------------------
// OUTER DATA STRUCTURE: SEGMENT TREE (Handles Rows)
// ---------------------------------------------------------
struct SegNode {
int left_child;
int right_child;
int treap_root;
};
const int MAX_SEG_NODES = 800000; // Nu * log(R) approx
SegNode seg_pool[MAX_SEG_NODES];
int seg_ptr = 1;
int get_seg_node() {
int idx = seg_ptr++;
seg_pool[idx].left_child = 0;
seg_pool[idx].right_child = 0;
seg_pool[idx].treap_root = 0;
return idx;
}
int root_seg = 0;
int ROWS, COLS;
// Get value of a specific column from a SegNode's treap
// We treat this as a range query [col, col]
ll get_val_at_col(int seg_idx, int col) {
if (seg_idx == 0) return 0;
return treap_query(seg_pool[seg_idx].treap_root, col, col);
}
void update_seg(int &node, int r_start, int r_end, int P, int Q, ll K) {
if (node == 0) node = get_seg_node();
// 1. If leaf row, update simple value
if (r_start == r_end) {
treap_update(seg_pool[node].treap_root, Q, K);
return;
}
int mid = r_start + (r_end - r_start) / 2;
if (P <= mid) {
update_seg(seg_pool[node].left_child, r_start, mid, P, Q, K);
} else {
update_seg(seg_pool[node].right_child, mid + 1, r_end, P, Q, K);
}
// 2. Internal node: Update its Treap based on children
ll val_left = get_val_at_col(seg_pool[node].left_child, Q);
ll val_right = get_val_at_col(seg_pool[node].right_child, Q);
ll new_val = gcd2(val_left, val_right);
treap_update(seg_pool[node].treap_root, Q, new_val);
}
ll query_seg(int node, int r_start, int r_end, int P, int Q, int U, int V) {
if (node == 0 || r_start > U || r_end < P) return 0;
// If fully contained in row range, query the Treap for column range
if (P <= r_start && r_end <= U) {
return treap_query(seg_pool[node].treap_root, Q, V);
}
int mid = r_start + (r_end - r_start) / 2;
return gcd2(query_seg(seg_pool[node].left_child, r_start, mid, P, Q, U, V),
query_seg(seg_pool[node].right_child, mid + 1, r_end, P, Q, U, V));
}
// ---------------------------------------------------------
// INTERFACE IMPLEMENTATION
// ---------------------------------------------------------
void init(int R, int C) {
ROWS = R;
COLS = C;
treap_ptr = 1;
seg_ptr = 1;
root_seg = 0;
srand(2013); // Fixed seed for reproducibility
}
void update(int P, int Q, long long K) {
// Limits: P is row 0..R-1, Q is col 0..C-1
update_seg(root_seg, 0, ROWS - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query_seg(root_seg, 0, ROWS - 1, P, Q, U, V);
}
