#include "game.h"
#include <cassert>
#include <forward_list>
#include <map>
//#include "ezprint.h"
#include <iostream>
#include <set>
using namespace std;
enum class Dim {ROW, COL};
template<Dim D>
class Bar {
using type = int;
};
template<Dim D>
class Foo {
Bar<D>::type x;
};
template<> class Bar<Dim::ROW> {
using type = map<Foo<Dim::COL>*, long long>;
};
template<> class Bar<Dim::COL> {
using type = set<Foo<Dim::COL> >;
};
// Foo<map<decltype(byC)*, long long> > byR;
// Foo<set<decltype(byR)::iterator> > byC;
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();
}
template<Dim D>
struct PayloadType {
using type = void;
};
template<Dim D>
class LazySegTree {
public:
struct Node {
private:
Node *left, *right;
// The uld (unique lowest descendant) of a node is defined as follows:
// uld(n) =
// if n has exactly 1 child, then uld(n's child)
// else n
//
// The idea is that for segment tree purposes, uld(n) has the "equivalent content"
// of n, and so can be used in place of n.
Node *uld;
Node() : left(nullptr), right(nullptr), uld(nullptr) {}
Node(const Node &) = delete;
Node(Node &&) = delete;
Node &operator=(const Node &) = delete;
int nChildren() const { return (left ? 1 : 0) + (right ? 1 : 0);}
// Node *uniqueChild() const {
// assert(nChildren() == 1);
// return left ? left : right;
// }
public:
Node *getL() const { return left ? left->uld : nullptr; }
Node *getR() const { return right ? right->uld : nullptr; }
PayloadType<D>::type payload;
friend class LazySegTree;
};
struct NodePtrIvl {
Node *node;
Interval ivl;
NodePtrIvl leftHalf() const { return {node->left, ivl.leftHalf()};}
NodePtrIvl rightHalf() const { return {node->right, ivl.rightHalf()};}
};
private:
NodePtrIvl root;
void decompose(const NodePtrIvl &nodePtrIvl, const Interval &queryIvl, forward_list<Node *> &ids) const {
Node *node = nodePtrIvl.node;
Interval nodeIvl = nodePtrIvl.ivl;
assert(nodeIvl.contains(queryIvl));
if(nodeIvl == queryIvl) {
assert(node->uld);
ids.push_front(node->uld);
return;
}
auto leftIvl = nodeIvl.leftHalf();
auto rightIvl = nodeIvl.rightHalf();
if(node->left && intersects(leftIvl, queryIvl)) {
decompose(nodePtrIvl.leftHalf(), intersection(leftIvl, queryIvl), ids);
}
if(node->right && intersects(rightIvl, queryIvl)) {
decompose(nodePtrIvl.rightHalf(), intersection(rightIvl, queryIvl), ids);
}
}
void printInternal(const NodePtrIvl &nodePtrIvl, int indent) {
for(int i=0; i<2*indent; ++i) { cout << " ";}
//ez::println("Node ", nodePtrIvl.node, " ivl ", nodePtrIvl.ivl, " uld ", nodePtrIvl.node->uld);
if(nodePtrIvl.node->left) {
for(int i=0; i<2*indent; ++i) { cout << " ";}
//ez::println("left:");
printInternal(nodePtrIvl.leftHalf(), indent+1);
}
if(nodePtrIvl.node->right) {
for(int i=0; i<2*indent; ++i) { cout << " ";}
//ez::println("right:");
printInternal(nodePtrIvl.rightHalf(), indent+1);
}
}
public:
inline LazySegTree(int N) : root(nullptr, {0,N}) {
assert(N >= 1);
}
struct Updates {
forward_list<Node *> nodes;
Node *pivotOld;
Node *pivotNew;
};
// Ensure that all nodes on the path from the root [0,N) to the
// leaf [x, x+1) exist. Returns all "relevant" nodes on this path,
// that is, those which don't have exactly one child.
// The returned list has nodes in the order from leaf to root.
Updates ensureNodesAndUpdates(int x) {
if(!root.node) { root.node = new Node(); }
assert(root.ivl.contains(x));
forward_list<Node *> ids;
NodePtrIvl cur = root;
Node *pendingToAssignUld[34]; // Upper bound on height
int pendingToAssignUldSize = 0;
Node *pivotOld = nullptr, *pivotNew = nullptr;
while(cur.node) {
assert(cur.ivl.contains(x));
pendingToAssignUld[pendingToAssignUldSize++] = cur.node;
NodePtrIvl nextCur {nullptr, {0,0}};
if(cur.ivl.length() > 1) {
int mid = cur.ivl.mid();
if(x < mid) {
if (!cur.node->left) { cur.node->left = new Node(); }
nextCur = cur.leftHalf();
} else {
if (!cur.node->right) { cur.node->right = new Node(); }
nextCur = cur.rightHalf();
}
}
if(cur.node->nChildren() == 2 && cur.node->uld != cur.node) {
// cur.node is not a pivot, but is about to become one below.
// cur.node->uld is a descendant of cur.node, and its information
// in the segment tree must be carried over to cur.node.
assert(!pivotOld); assert(!pivotNew);
pivotOld = cur.node->uld;
pivotNew = cur.node;
assert(pivotOld); assert(pivotNew);
}
if(cur.node->nChildren() != 1) {
for(int i=0; i<pendingToAssignUldSize; ++i) {
pendingToAssignUld[i]->uld = cur.node;
}
pendingToAssignUldSize = 0;
ids.push_front(cur.node);
}
cur = nextCur;
}
return {ids, pivotOld, pivotNew};
}
// 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 list
// is at most logarithmic in N.
forward_list<Node *> decomposeIntervalAndGetIds(const Interval &ivl) const {
forward_list<Node *> ids;
if(root.node) {
decompose(root, ivl, ids);
}
return ids;
}
// void print() {
// printInternal(root, 0);
// }
};
template<> struct PayloadType<Dim::ROW> {
using type=map<LazySegTree<Dim::COL>::Node *, long long>;
};
template<> struct PayloadType<Dim::COL> {
//using type=forward_list<PayloadType<Dim::ROW>::type::iterator>;
using type=map<LazySegTree<Dim::ROW>::Node *, long long>;
};
LazySegTree<Dim::ROW> Rtree(1);
LazySegTree<Dim::COL> Ctree(1);
typedef LazySegTree<Dim::ROW>::Node * RNodeId;
typedef LazySegTree<Dim::COL>::Node * CNodeId;
inline long long getGcd(RNodeId r, CNodeId c) {
long long x = getOrDefault(r->payload, c, 0LL);
long long y = getOrDefault(c->payload, r, 0LL);
assert(x==y);
return x;
}
void init(int R, int C) {
Rtree = LazySegTree<Dim::ROW>(R);
Ctree = LazySegTree<Dim::COL>(C);
}
void update(int P, int Q, long long K) {
// Each of these is ordered from leaf to root.
auto rUpdates = Rtree.ensureNodesAndUpdates(P);
auto cUpdates = Ctree.ensureNodesAndUpdates(Q);
// First we do some transformations on data structure which
// keeps it equivalent, by adding the pivot nodes.
//ez::println("\n\n\n\nupdate P=", P, " Q=", Q, " K=", K, "\nRtree");
//Rtree.print();
//ez::println("\nCtree");
//Ctree.print();
//ez::println();
if(rUpdates.pivotOld) {
assert(rUpdates.pivotNew);
assert(rUpdates.pivotOld != rUpdates.pivotNew);
assert(rUpdates.pivotNew->payload.empty());
rUpdates.pivotNew->payload = rUpdates.pivotOld->payload;
for(auto [c, val] : rUpdates.pivotOld->payload) {
auto [it, wasInserted] = c->payload.insert({rUpdates.pivotNew, val});
assert(wasInserted);
}
}
if(cUpdates.pivotOld) {
assert(cUpdates.pivotNew);
assert(cUpdates.pivotOld != cUpdates.pivotNew);
assert(cUpdates.pivotNew->payload.empty());
cUpdates.pivotNew->payload = cUpdates.pivotOld->payload;
for(auto [r, val] : cUpdates.pivotOld->payload) {
auto [it, wasInserted] = r->payload.insert({cUpdates.pivotNew, val});
assert(wasInserted);
}
}
// The equivalent transformations are done, now we do
// the actual insert
forward_list<RNodeId> rIds = rUpdates.nodes;
forward_list<CNodeId> cIds = cUpdates.nodes;
assert(!rIds.empty());
assert(!cIds.empty());
//ez::println("rIds ", rIds);
//ez::println("cIds ", cIds);
for (auto rId : rIds)
for (auto cId : cIds) {
if (rId == rIds.front() && cId == cIds.front()) { // base case
rId->payload[cId] = cId->payload[rId] = 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 (rId == rIds.front()) {
// cId->getL or cId->getR() can be nullptr 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.
rId->payload[cId] = cId->payload[rId] =
gcd2(getGcd(rId, cId->getL()), getGcd(rId, cId->getR()));
} else {
rId->payload[cId] = cId->payload[rId] =
gcd2(getGcd(rId->getL(), cId), getGcd(rId->getR(), cId));
}
}
//ez::println("After update ", gcds);
}
long long calculate(int P, int Q, int U, int V) {
auto rIds = Rtree.decomposeIntervalAndGetIds({P, U+1});
auto cIds = Ctree.decomposeIntervalAndGetIds({Q, V+1});
long long ans = 0;
for(auto rId : rIds)
for(auto cId : cIds) {
ans = gcd2(ans, getGcd(rId, cId));
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;
}
