#include "game.h"
#include <cassert>
#include <vector>
#include <map>
using namespace std;
long long gcd2(long long X, long long Y);
template<class Key, class T, class Compare, class Allocator>
T getOrDefault(const map<Key, T, Compare, Allocator> &m, const Key &k, const T &def) {
auto it = m.find(k);
return it == m.end() ? def : it->second;
}
// Intended for nonempty intervals.
struct Interval {
int L, U;
inline bool operator==(const Interval &other) const = default;
inline int length() const {return U-L;}
inline bool contains(const Interval &x) const { return L <= x.L && x.U <= U; }
inline bool contains(int x) const { return L <= x && x < U;}
inline bool nonempty() const { return length() > 0; }
inline int mid() const { return L + (U-L)/2;}
inline Interval leftHalf() const { return Interval {L, mid()};}
inline Interval rightHalf() const { return Interval {mid(), U};}
};
// Intended for intervals known to intersect.
inline Interval intersection(const Interval &x, const Interval &y) {
return {max(x.L, y.L), min(x.U, y.U)};
}
inline bool intersects(const Interval &x, const Interval &y) {
return intersection(x, y).nonempty();
}
class LazySegTreeIntervals {
private:
int nextId = 0;
struct Node {
int id;
Interval ivl;
Node *left, *right;
Node(int id_, const Interval &ivl_) : id(id_), ivl(ivl_), left(nullptr), right(nullptr) {}
inline int length() const { return ivl.length();}
};
Node *root;
int N;
inline Node *createNewNode(const Interval &ivl) {
return new Node(nextId++, ivl);
}
void decompose(const Node *node, const Interval &queryIvl, vector<int> &ids) const {
assert(node->ivl.contains(queryIvl));
if(node->ivl == queryIvl) {
ids.push_back(node->id);
return;
}
if(node->left && intersects(node->left->ivl, queryIvl)) {
decompose(node->left, intersection(node->left->ivl, queryIvl), ids);
}
if(node->right && intersects(node->right->ivl, queryIvl)) {
decompose(node->right, intersection(node->right->ivl, queryIvl), ids);
}
}
public:
struct ParentChildIds {
int p, c1, c2;
};
private:
inline ParentChildIds getParentChildId(Node *node) {
return {node->id, node->left ? node->left->id : NO_ID, node->right? node->right->id : NO_ID};
}
public:
inline LazySegTreeIntervals(int N_) : N(N_) {
assert(N >= 1);
root = createNewNode({0,N});
}
constexpr static int NO_ID = -1;
// Ensure that all nodes on the path from the root [0,N) to the
// leaf [x, x+1) exist. For each such node, returns a tuple
// with the id of that node and both its children (or NO_ID if a child
// doesn't exist). These are retured in order from root to leaf.
vector<ParentChildIds> ensureNodesAndGetIds(int x) {
assert(0 <= x && x < N);
vector<ParentChildIds> ids;
ids.reserve(32); // Upper bound for maximum height of the tree for the maximum N
Node *cur = root;
while(true) {
assert(cur && cur->ivl.contains(x));
if(cur->ivl.length() == 1) {
ids.push_back(getParentChildId(cur));
break;
}
int mid = cur->ivl.mid();
if(x < mid) {
if (!cur->left) cur->left = createNewNode(cur->ivl.leftHalf());
ids.push_back(getParentChildId(cur));
cur = cur->left;
} else {
if (!cur->right) cur->right = createNewNode(cur->ivl.rightHalf());
ids.push_back(getParentChildId(cur));
cur = cur->right;
}
}
return ids;
}
// Try to decompose [a,b) into constituent intervals as
// if this was a full segtree. Let X be the set of values for
// which createIntervalsAndGetIds has been called.
// Consider the ids returned by this method, and
// let Y be the union of their corresponding intervals.
// Then we have Y intersection X = [a,b) intersection X.
// If this was a full segtree, we would have Y = [a,b).
// Of course, we also have that the size of the returned vector
// is at most logarithmic in N.
vector<int> decomposeIntervalAndGetIds(const Interval &ivl) const {
vector<int> ids;
decompose(root, ivl, ids);
return ids;
}
};
LazySegTreeIntervals Rtree(1), Ctree(1);
// A key (x,y) corresponds to node with id x in Rtree and
// a node with id y in Ctree. Each of those nodes represent an
// interval of indices. Their product represents a subrectangle
// of cells. The value is the gcd of the values in those cells.
map<pair<int, int>, long long> gcds;
void init(int R, int C) {
Rtree = LazySegTreeIntervals(R);
Ctree = LazySegTreeIntervals(C);
}
void update(int P, int Q, long long K) {
// Each of these is ordered from root to leaf.
vector<LazySegTreeIntervals::ParentChildIds> rIds = Rtree.ensureNodesAndGetIds(P);
vector<LazySegTreeIntervals::ParentChildIds> cIds = Ctree.ensureNodesAndGetIds(Q);
assert(!rIds.empty());
assert(!cIds.empty());
for (auto rit = rIds.rbegin(); rit != rIds.rend(); ++rit)
for (auto cit = cIds.rbegin(); cit != cIds.rend(); ++cit) {
if (rit == rIds.rbegin() && cit == cIds.rbegin()) { // base case
gcds[{rIds.rbegin()->p, cIds.rbegin()->p}] = K;
continue;
}
// We have a rectangle which can be split in half in two ways
// We can choose either arbitrarily, except for a 1xN or Nx1
// rectangle, in which case there is only one choice.
if (rit == rIds.rbegin()) {
// cit->c1 or cit->c2 can be NO_ID if that child doesn't exist (hasn't been populated)
// in the tree. This is not a problem, since in that case that key doesn't exist
// in the map, so 0 is returned, as desired.
gcds[{rit->p, cit->p}] =
gcd2(getOrDefault(gcds, {rit->p, cit->c1}, 0LL), getOrDefault(gcds, {rit->p, cit->c2}, 0LL));
} else {
gcds[{rit->p, cit->p}] =
gcd2(getOrDefault(gcds, {rit->c1, cit->p}, 0LL), getOrDefault(gcds, {rit->c2, cit->p}, 0LL));
}
}
}
long long calculate(int P, int Q, int U, int V) {
vector<int> rIds = Rtree.decomposeIntervalAndGetIds({P, U+1});
vector<int> cIds = Ctree.decomposeIntervalAndGetIds({Q, V+1});
long long ans = 0;
for(int rId : rIds)
for(int cId : cIds) {
ans = gcd2(ans, getOrDefault(gcds, {rId, cId}, 0LL));
if (ans==1) { return 1; }
}
return ans;
}
inline 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;
}
