constexpr int BR = 3;
/* Here we use a segment tree with a branching factor of BR which
* could be more than the standard 2. If a node represents an interval
* of length T, its chilren are defined as follows: If T is 1, this
* is a leaf node with no children. Otherwise, it has up to BR children,
* as follows. Let's start with exactly BR childre, with every child
* having T/BR or T/BR + 1 elements. The leftmost T%BR children have
* T/BR + 1 elements, and the remaining have T/BR elements.
* The leftmost T%BR children contribute T%BR * (T/BR + 1) elements.
* The remaining BR - T%BR children contribute (BR - T%BR) * (T/BR)
* elements. Adding the two, we get
* T%BR * (T/BR + 1) + (BR - T%BR) * (T/BR)
* = T%BR * T/BR + T%BR + BR * T/BR - T%BR * T/BR
* = BR * T/BR + T%BR
* = T
* as expected.
*
* Finally, any nodes with zero elements are deleted.
*/
#include "game.h"
#include <cassert>
#include <vector>
#include <map>
#include <ranges>
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 vector<Interval> children() const {
int T = length();
if (T == 1) {
return vector<Interval>();
}
vector<Interval> ans;
int x = L;
for(auto _ : views::iota(0, T%BR)) {
ans.push_back({x, x + T/BR + 1});
x += T/BR + 1;
}
if (T/BR != 0) {
for(auto _ : views::iota(T%BR, BR)) {
ans.push_back({x, x + T/BR});
x += T/BR;
}
}
//DELETEMEassert(x == U);
return ans;
}
// returns whichth child of this node x belongs to.
inline int getChildIndex(int x) const {
//DELETEMEassert(contains(x));
int T = length();
// This interval is divided into BR intervals:
// 1. First T%BR have length T/BR + 1
// 2. Remaining have length T/BR
// y is position relative to the beginning of this interval.
int y = x - L;
// Is x in the first T%BR children?
int ans;
if(y < (T%BR) * (T/BR + 1)) {
ans = y/(T/BR + 1);
} else {
// z is position relative to the beginning of the second set of child intervals.
int z = y - (T%BR) * (T/BR + 1);
ans = T%BR + z/(T/BR);
}
//DELETEMEassert(0 <= ans);
//DELETEMEassert(ans < BR);
//DELETEMEassert(children().at(ans).contains(x));
return ans;
}
};
// 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 {
public:
struct Node {
// We can avoid having Interval here, but not clear if this optimization is useful.
//Interval ivl;
Node *children[BR];
Node(){ fill(children, children + BR, nullptr);}
};
private:
// The interval must correspond to the node.
struct NodePtrIvl {
Node *node;
Interval ivl;
inline vector<NodePtrIvl> children() const {
vector<Interval> c = ivl.children();
vector<NodePtrIvl> ans;
ans.reserve(c.size());
for(int i=0; i<c.size(); ++i) {
ans.emplace_back(node->children[i], c[i]);
}
return ans;
}
};
NodePtrIvl root;
inline Node *createNewNode() {
return new Node();
}
void decompose(const NodePtrIvl &n, const Interval &queryIvl, vector<Node *> &ids) const {
//DELETEMEassert(n.ivl.contains(queryIvl));
if(n.ivl == queryIvl) {
ids.push_back(n.node);
return;
}
for(auto child : n.children()) {
if(child.node && intersects(child.ivl, queryIvl)) {
decompose(child, intersection(child.ivl, queryIvl), ids);
}
}
}
public:
inline LazySegTreeIntervals(int N) : root({createNewNode(), {0, N}}) {
//DELETEMEassert(N >= 1);
}
// Ensure that all nodes on the path from the root [0,N) to the
// leaf [x, x+1) exist. These are retured in order from root to leaf.
vector<Node *> ensureNodesAndGetIds(int x) {
//DELETEMEassert(root.ivl.contains(x));
vector<Node *> ids;
NodePtrIvl cur = root;
while(true) {
//DELETEMEassert(cur.node);
//DELETEMEassert(cur.ivl.contains(x));
if(cur.ivl.length() == 1) {
ids.push_back(cur.node);
break;
}
int childIndex = cur.ivl.getChildIndex(x);
if(!cur.node->children[childIndex]) {
cur.node->children[childIndex] = createNewNode();
}
ids.push_back(cur.node);
cur = cur.children()[childIndex]; // can optimize, no need to compute all children
}
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<Node *> decomposeIntervalAndGetIds(const Interval &ivl) const {
vector<Node *> 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<LazySegTreeIntervals::Node *, LazySegTreeIntervals::Node *>, 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::Node *> rIds = Rtree.ensureNodesAndGetIds(P);
vector<LazySegTreeIntervals::Node *> cIds = Ctree.ensureNodesAndGetIds(Q);
//DELETEMEassert(!rIds.empty());
//DELETEMEassert(!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(), *cIds.rbegin()}] = K;
continue;
}
// We have a rectangle which can be split in BR rectangles horizontally or vertically.
// We can choose either arbitrarily, except for a 1xN or Nx1
// rectangle, in which case there is only one choice.
long long &z = gcds[{*rit, *cit}];
z=0;
if (rit == rIds.rbegin()) {
// q 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.
for(auto q : (*cit)->children) {
z = gcd2(z, getOrDefault(gcds, {*rit, q}, 0LL));
}
} else {
for(auto q : (*rit)->children) {
z = gcd2(z, getOrDefault(gcds, {q, *cit}, 0LL));
}
}
}
}
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, 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;
}
