#include "game.h" #define ll long long const int NODE_Y_MAX = 8e6; const int NODE_X_MAX = 4e6; const int NMAX = 1e9; 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; } int n, m, root_x; int nodes_y, nodes_x; struct NodeY { ll gcd; int left, right; NodeY() : gcd(0), left(0), right(0) {} }aint_y[NODE_Y_MAX + 1]; struct NodeX { int root_y; int left, right; NodeX() : root_y(0), left(0), right(0) {} }aint_x[NODE_X_MAX + 1]; int create_node_x() { nodes_x++; return nodes_x; } int create_node_y() { nodes_y++; return nodes_y; } void updateY(int& node, int left, int right, int pos, ll value) { if(!node) { node = create_node_y(); } if(left == right) { aint_y[node].gcd = value; return; } int mid = (left + right) / 2; if(pos <= mid) { updateY(aint_y[node].left, left, mid, pos, value); } else { updateY(aint_y[node].right, mid + 1, right, pos, value); } aint_y[node].gcd = gcd2(aint_y[aint_y[node].left].gcd, aint_y[aint_y[node].right].gcd); } ll queryY(int node, int left, int right, int qleft, int qright) { if(!node || left > qright || right < qleft) { return 0; } if(left >= qleft && right <= qright) { return aint_y[node].gcd; } int mid = (left + right) / 2; return gcd2(queryY(aint_y[node].left, left, mid, qleft, qright), queryY(aint_y[node].right, mid + 1, right, qleft, qright)); } void updateX(int& node, int left_x, int right_x, int pos_x, int pos_y, ll value) { if(!node) { node = create_node_x(); } if(left_x == right_x) { updateY(aint_x[node].root_y, 1, m, pos_y, value); return; } int mid_x = (left_x + right_x) / 2; if(pos_x <= mid_x) { updateX(aint_x[node].left, left_x, mid_x, pos_x, pos_y, value); } else { updateX(aint_x[node].right, mid_x + 1, right_x, pos_x, pos_y, value); } ll new_gcd = gcd2(queryY(aint_x[aint_x[node].left].root_y, 1, m, pos_y, pos_y), queryY(aint_x[aint_x[node].right].root_y, 1, m, pos_y, pos_y)); updateY(aint_x[node].root_y, 1, m, pos_y, new_gcd); } ll queryX(int node, int left_x, int right_x, int qleft_x, int qleft_y, int qright_x, int qright_y) { if(!node || left_x > qright_x || right_x < qleft_x) { return 0; } if(left_x >= qleft_x && right_x <= qright_x) { return queryY(aint_x[node].root_y, 1, m, qleft_y, qright_y); } int mid_x = (left_x + right_x) / 2; return gcd2(queryX(aint_x[node].left, left_x, mid_x, qleft_x, qleft_y, qright_x, qright_y), queryX(aint_x[node].right, mid_x + 1, right_x, qleft_x, qleft_y, qright_x, qright_y)); } void init(int R, int C) { n = R; m = C; root_x = create_node_x(); } void update(int P, int Q, long long K) { P++; Q++; updateX(root_x, 1, n, P, Q, K); } long long calculate(int P, int Q, int U, int V) { P++; Q++; U++; V++; return queryX(root_x, 1, n, P, Q, U, V); }