#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int r, c;
struct NodeCol {
NodeCol *left, *right;
long long value;
NodeCol() : left(nullptr), right(nullptr), value(0) {}
};
struct NodeRow {
NodeRow *left, *right;
NodeCol *col;
NodeRow() : left(nullptr), right(nullptr), col(nullptr) {}
};
struct Dynamic2DGCD {
NodeRow* root = new NodeRow();
// Merge two column nodes
long long merge_col(NodeCol* a, NodeCol* b) {
long long val_a = a ? a->value : 0;
long long val_b = b ? b->value : 0;
return __gcd(val_a, val_b);
}
// Update column tree at column 'col_id'
void update_col(NodeCol*& node, int start, int end, int col_id, long long val) {
if (!node) node = new NodeCol();
if (start == end) {
node->value = val;
return;
}
int mid = (start + end) / 2;
if (col_id <= mid) update_col(node->left, start, mid, col_id, val);
else update_col(node->right, mid + 1, end, col_id, val);
node->value = merge_col(node->left, node->right);
}
// Merge two column trees (used for internal row nodes)
long long query_col(NodeCol* node, int start, int end, int l, int r) {
if (!node || start > r || end < l) return 0;
if (l <= start && end <= r) return node->value;
int mid = (start + end) / 2;
return __gcd(query_col(node->left, start, mid, l, r),
query_col(node->right, mid + 1, end, l, r));
}
// Update row tree at row 'row_id' and column 'col_id'
void update_row(NodeRow*& node, int start, int end, int row_id, int col_id, long long val) {
if (!node) node = new NodeRow();
if (start == end) {
// Leaf row: update its column tree
update_col(node->col, 0, c - 1, col_id, val);
return;
}
int mid = (start + end) / 2;
if (row_id <= mid) update_row(node->left, start, mid, row_id, col_id, val);
else update_row(node->right, mid + 1, end, row_id, col_id, val);
// Internal row: merge left and right children for this column
long long left_val = node->left ? query_col(node->left->col, 0, c - 1, col_id, col_id) : 0;
long long right_val = node->right ? query_col(node->right->col, 0, c - 1, col_id, col_id) : 0;
update_col(node->col, 0, c - 1, col_id, __gcd(left_val, right_val));
}
// Query row tree for rows [row_l, row_r] and columns [col_l, col_r]
long long query_row(NodeRow* node, int start, int end, int row_l, int row_r, int col_l, int col_r) {
if (!node || start > row_r || end < row_l) return 0;
if (row_l <= start && end <= row_r) return query_col(node->col, 0, c - 1, col_l, col_r);
int mid = (start + end) / 2;
return __gcd(query_row(node->left, start, mid, row_l, row_r, col_l, col_r),
query_row(node->right, mid + 1, end, row_l, row_r, col_l, col_r));
}
// Public API
void update(int row_id, int col_id, long long val) {
update_row(root, 0, r - 1, row_id, col_id, val);
}
long long query(int row_l, int col_l, int row_r, int col_r) {
return query_row(root, 0, r - 1, row_l, row_r, col_l, col_r);
}
} tr;
// API functions
void init(int R, int C) {
r = R; c = C;
}
void update(int P, int Q, long long K) {
tr.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return tr.query(P, Q, U, V);
}
