#include "game.h"
#include <iostream>
using namespace std;
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;
}
struct Seg {
Seg *l, *r;
long long sum;
Seg () {
l = r = nullptr;
sum = 0;
}
};
struct Node {
Node *l, *r;
Seg *segmentTree;
long long sum;
Node () {
l = r = nullptr;
sum = 0;
}
};
Node *root;
int _R, _C;
void update_coluna (Seg *&cur, int l, int r, int coluna, long long delta, bool is_merge, Seg *esq, Seg *dir) {
if (l > coluna || r < coluna) return;
if (l == coluna && r == coluna) {
if (is_merge == false) {
cur -> sum = delta;
} else {
cur -> sum = gcd2 ( (esq ? esq -> sum : 0) , (dir ? dir -> sum : 0) );
}
return;
}
int mid = l + (r - l) / 2;
if (mid >= coluna) {
if (!cur -> l) cur -> l = new Seg;
update_coluna (cur -> l, l, mid, coluna, delta, is_merge, (esq && esq -> l ? esq -> l : nullptr), (dir && dir -> l ? dir -> l: nullptr) );
}
if (mid + 1 <= coluna) {
if (!cur -> r) cur -> r = new Seg;
update_coluna (cur -> r, mid + 1, r, coluna, delta, is_merge, (esq && esq -> r ? esq -> r : nullptr), (dir && dir -> r ? dir -> r : nullptr) );
}
if (is_merge == false) {
cur -> sum = gcd2 ( (cur -> l ? cur -> l -> sum : 0), (cur -> r ? cur -> r -> sum : 0) );
// cout << l << ' ' << r << ' ' << cur -> sum << '\n';
// cout << cur << '\n';
} else {
cur -> sum = gcd2 ( (esq ? esq -> sum : 0), (dir ? dir -> sum : 0) );
}
}
void update_linha (Node *&cur, int l, int r, int linha, long long delta, int coluna) {
if (l > linha || r < linha) return;
if (l == linha && r == linha) {
if (!cur -> segmentTree) cur -> segmentTree = new Seg;
// CALL UPDATE_COLUNA
// cout << "ENTROU: " << cur << '\n';
update_coluna (cur -> segmentTree, 0, _C - 1, coluna, delta, false, nullptr, nullptr);
return;
}
int mid = l + (r - l) / 2;
if (mid >= linha) {
if (!cur -> l) cur -> l = new Node;
update_linha (cur -> l, l, mid, linha, delta, coluna);
}
if (mid + 1 <= linha) {
if (!cur -> r) cur -> r = new Node;
update_linha (cur -> r, mid + 1, r, linha, delta, coluna);
}
if (!cur -> segmentTree) cur -> segmentTree = new Seg;
update_coluna (cur -> segmentTree, 0, _C - 1, coluna, delta, true, (cur -> l ? cur -> l -> segmentTree: nullptr), (cur -> r ? cur -> r -> segmentTree : nullptr) );
// MERGE
}
void init(int R, int C) {
root = new Node;
_R = R;
_C = C;
}
void update(int P, int Q, long long K) {
update_linha (root, 0, _R - 1, P, K, Q);
}
long long query_coluna (Seg* cur, int l, int r, int coluna_inicial, int coluna_final) {
if (!cur || l > coluna_final || r < coluna_inicial) return 0;
if (l >= coluna_inicial && r <= coluna_final) {
//cout << cur << '\n';
//cout << "A: " << coluna_inicial << ' ' << coluna_final << ' ' << cur -> sum << '\n';
return cur -> sum;
}
int mid = l + (r - l) / 2;
return gcd2 ( query_coluna (cur -> l, l, mid, coluna_inicial, coluna_final ),
query_coluna (cur -> r, mid + 1, r, coluna_inicial, coluna_final ) );
}
long long query_linha (Node* cur, int l, int r, int linha_inicial, int linha_final, int coluna_inicial, int coluna_final) {
if (!cur || l > linha_final || r < linha_inicial) return 0;
if (l >= linha_inicial && r <= linha_final) {
// cout << "Q: " << cur << '\n';
return query_coluna (cur -> segmentTree, 0, _C - 1, coluna_inicial, coluna_final);
}
int mid = l + (r - l) / 2;
return gcd2 ( query_linha (cur -> l, l, mid, linha_inicial, linha_final, coluna_inicial, coluna_final ),
query_linha (cur -> r, mid + 1, r, linha_inicial, linha_final, coluna_inicial, coluna_final ) );
}
long long calculate(int P, int Q, int U, int V) {
return query_linha (root, 0, _R - 1, P, U, Q, V);
}
