#include "game.h"
#include <iostream>
#include <numeric>
#include <vector>
using i32 = int32_t;
using i64 = long long;
auto midpoint(i32 l, i32 r) -> i32 { return l + (r - l) / 2; }
struct Node {
Node *l, *r;
i32 from, to;
i64 val;
explicit Node(i32 from, i32 to)
: l{nullptr}, r{nullptr}, from{from}, to{to}, val{0} {}
explicit Node(i32 len) : Node(0, len) {}
auto left() -> Node * { return l ?: l = new Node(from, midpoint(from, to)); }
auto right() -> Node * { return r ?: r = new Node(midpoint(from, to), to); }
void set(i32 pos, i64 i) {
if (to - from > 1) {
auto m = midpoint(from, to);
if (pos < m)
left()->set(pos, i);
else
right()->set(pos, i);
val = 0;
if (l)
val = std::gcd(val, l->val);
if (r)
val = std::gcd(val, r->val);
} else {
val = i;
}
}
auto query(i32 l, i32 r) -> i64 {
if (l <= from && to <= r) {
// std::cerr << "including " << from << ".." << to << "\n";
return val;
} else if (to <= l || r <= from) {
// std::cerr << "excluding " << from << ".." << to << "\n";
return 0;
} else {
return std::gcd(left()->query(l, r), right()->query(l, r));
}
}
};
namespace {
std::vector<Node> rows;
i32 h, w;
} // namespace
void init(i32 R, i32 C) {
rows.reserve(R);
for (i32 i = 0; i < R; i++)
rows.emplace_back(C);
h = R;
w = C;
}
void update(i32 P, i32 Q, i64 K) {
// std::cerr << "Setting " << P << " " << Q << " to " << K << "\n";
rows[P].set(Q, K);
}
auto calculate(i32 P, i32 Q, i32 U, i32 V) -> i64 {
// std::cerr << "range: " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
i64 val = 0;
for (i32 r = P; r <= U; r++) {
// std::cerr << "row " << r << " res " << rows[r].query(Q, V + 1) << '\n';
val = std::gcd(val, rows[r].query(Q, V + 1));
}
return val;
}
