#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int r, c;
// Column node for 2D segment tree
struct NodeCol {
NodeCol *left, *right;
long long answer;
NodeCol() {
left = right = nullptr;
answer = 0;
}
};
// Row node for 2D segment tree
struct NodeRow {
NodeRow *left, *right;
NodeCol *col;
NodeRow() {
left = right = nullptr;
col = nullptr;
}
};
struct DynamicSegmentTree2D {
NodeRow *root = new NodeRow();
// Update column segment tree
void update_col(NodeCol *cur, NodeRow *cur_row, int start, int end,
int col_id, int row_start, int row_end, long long value) {
if (start == end) {
if (row_start == row_end) {
cur->answer = value;
} else {
long long left_val = 0, right_val = 0;
if (cur_row->left && cur_row->left->col) left_val = cur_row->left->col->answer;
if (cur_row->right && cur_row->right->col) right_val = cur_row->right->col->answer;
cur->answer = __gcd(left_val, right_val);
}
return;
}
int mid = (start + end) / 2;
if (col_id <= mid) {
if (!cur->left) cur->left = new NodeCol();
update_col(cur->left, cur_row, start, mid, col_id, row_start, row_end, value);
} else {
if (!cur->right) cur->right = new NodeCol();
update_col(cur->right, cur_row, mid + 1, end, col_id, row_start, row_end, value);
}
long long left_val = cur->left ? cur->left->answer : 0;
long long right_val = cur->right ? cur->right->answer : 0;
cur->answer = __gcd(left_val, right_val);
}
// Update row segment tree
void update_row(NodeRow *cur, int start, int end,
int row_id, int col_id, long long value) {
if (start != end) {
int mid = (start + end) / 2;
if (row_id <= mid) {
if (!cur->left) cur->left = new NodeRow();
update_row(cur->left, start, mid, row_id, col_id, value);
} else {
if (!cur->right) cur->right = new NodeRow();
update_row(cur->right, mid + 1, end, row_id, col_id, value);
}
}
if (!cur->col) cur->col = new NodeCol();
update_col(cur->col, cur, 0, c - 1, col_id, start, end, value);
}
// Query column segment tree
long long query_col(NodeCol *cur, int start, int end, int l, int r) {
if (!cur || start > r || end < l) return 0;
if (l <= start && end <= r) return cur->answer;
int mid = (start + end) / 2;
return __gcd(query_col(cur->left, start, mid, l, r),
query_col(cur->right, mid + 1, end, l, r));
}
// Query row segment tree
long long query_row(NodeRow *cur, int start, int end,
int l, int r, int col_l, int col_r) {
if (!cur || start > r || end < l) return 0;
if (l <= start && end <= r) return query_col(cur->col, 0, c - 1, col_l, col_r);
int mid = (start + end) / 2;
return __gcd(query_row(cur->left, start, mid, l, r, col_l, col_r),
query_row(cur->right, mid + 1, end, l, r, col_l, col_r));
}
// Public update function
void update(int r1, int c1, long long value) {
update_row(root, 0, r - 1, r1, c1, value);
}
// Public query function
long long query(int r1, int c1, int r2, int c2) {
return query_row(root, 0, r - 1, r1, r2, c1, c2);
}
} tr;
// API functions for game.h
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);
}
