#include "game.h"
#include <iostream>
using namespace std;
typedef long long ll;
int n, m;
ll gcd(ll a, ll b) {
while (a && b) {
(a > b) ? a %= b : b %= a;
}
return a + b;
}
struct Nodex {
int left;
int right;
Nodex* ls;
Nodex* rs;
ll val;
};
struct Nodey {
int left;
int right;
Nodey* ls;
Nodey* rs;
Nodex* root;
};
Nodey* Root;
ll queryX(Nodex* v, int C1, int C2) {
if (v->right < C1 || v->left > C2) return 0;
if (v->left >= C1 && v->right <= C2) {
return v->val;
}
if (v->ls == nullptr) {
int mid = (v->left + v->right) / 2;
Nodex* ls = new Nodex{ v->left, mid, nullptr, nullptr, v->val };
Nodex* rs = new Nodex{ mid + 1, v->right, nullptr, nullptr, v->val };
v->ls = ls;
v->rs = rs;
return gcd(queryX(v->ls, C1, C2), queryX(v->rs, C1, C2));
}
return gcd(queryX(v->ls, C1, C2), queryX(v->rs, C1, C2));
}
ll queryY(Nodey* v, int R1, int C1, int R2, int C2) {
if (v->left > R2 || v->right < R1) {
return 0;
}
if (v->root == nullptr) {
Nodex* rt = new Nodex{ 1, m, nullptr, nullptr, 0 };
v->root = rt;
}
if (v->left >= R1 && v->right <= R2) {
return queryX(v->root, C1, C2);
}
if (v->ls == nullptr) {
int mid = (v->left + v->right) / 2;
Nodey* ls = new Nodey{ v->left, mid, nullptr, nullptr, new Nodex{1, m, nullptr, nullptr, 0} };
Nodey* rs = new Nodey{ mid + 1, v->right, nullptr, nullptr, new Nodex{1, m, nullptr, nullptr, 0} };
v->ls = ls;
v->rs = rs;
}
return gcd(queryY(v->ls, R1, C1, R2, C2), queryY(v->rs, R1, C1, R2, C2));
}
void Updatex(Nodex* v, int C, ll val) {
if (v->left > C || v->right < C) return;
if (v->left == v->right) {
v->val = val;
return;
}
if (v->ls == nullptr) {
int mid = (v->left + v->right) / 2;
Nodex* ls = new Nodex{ v->left, mid, nullptr, nullptr, v->val };
Nodex* rs = new Nodex{ mid + 1, v->right, nullptr, nullptr, v->val };
Updatex(ls, C, val);
Updatex(rs, C, val);
v->val = gcd(ls->val, rs->val);
v->ls = ls;
v->rs = rs;
return;
}
Updatex(v->ls, C, val);
Updatex(v->rs, C, val);
v->val = gcd(v->ls->val, v->rs->val);
}
void Updatey(Nodey* v, int R, int C, ll val) {
if (v->left > R || v->right < R) return;
if (v->left == v->right) {
Updatex(v->root, C, val);
return;
}
if (v->ls == nullptr) {
int mid = (v->left + v->right) / 2;
Nodey* ls = new Nodey{ v->left, mid, nullptr, nullptr, new Nodex{1, m, nullptr, nullptr, 0} };
Nodey* rs = new Nodey{ mid + 1, v->right, nullptr, nullptr, new Nodex{1, m, nullptr, nullptr, 0} };
Updatey(ls, R, C, val);
Updatey(rs, R, C, val);
v->ls = ls;
v->rs = rs;
}
Updatey(v->ls, R, C, val);
Updatey(v->rs, R, C, val);
Updatex(v->root, C, gcd(queryX(v->ls->root, C, C), queryX(v->rs->root, C, C)));
}
void init(int R, int C) {
n = R;
m = C;
Root = new Nodey{ 1, n, nullptr, nullptr, new Nodex{ 1, m, nullptr, nullptr, 0 } };
}
void update(int R, int Q, long long K) {
Updatey(Root, R + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryY(Root, P + 1, Q + 1, U + 1, V + 1);
}
