#include "game.h"
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
// #define DEBUG
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
std::mt19937_64 rng(23);
i64 gcd(i64 a, i64 b, i64 c) {
return std::gcd(a, std::gcd(b, c));
}
int R, C;
struct treap {
struct node {
u64 wei = rng();
node *l = nullptr, *r = nullptr;
int pos;
i64 sum, val;
int lo, hi;
node() {}
node(int p, i64 v) : pos(p), sum(v), val(v), lo(p), hi(p) {}
};
node* root = nullptr;
treap() {}
treap(node* x) : root(x) {}
i64 sum(node* v) { return v ? v->sum : 0; }
void pull(node*& v) {
if (!v) {
return;
}
v->sum = gcd(sum(v->l), sum(v->r), v->val);
v->lo = (v->l ? v->l->lo : v->pos);
v->hi = (v->r ? v->r->hi : v->pos);
}
void merge(node*& v, node* l, node* r) {
if (!l || !r) {
v = (l ? l : r);
return;
}
if (l->wei < r->wei) {
merge(r->l, l, r->l);
v = r;
} else {
merge(l->r, l->r, r);
v = l;
}
pull(v);
}
void split(node* v, node*& l, node*& r, int p) {
if (!v) {
l = nullptr;
r = nullptr;
return;
}
if (v->pos < p) {
split(v->r, v->r, r, p);
l = v;
} else {
split(v->l, l, v->l, p);
r = v;
}
pull(l);
pull(r);
}
bool find(int pos) {
node* v = root;
while (v) {
if (v->pos == pos) {
return true;
} else if (v->pos < pos) {
v = v->r;
} else {
v = v->l;
}
}
return false;
}
void update(node* v, int p, i64 x) {
if (v->pos == p) {
v->val = x;
} else if (v->pos < p) {
update(v->r, p, x);
} else {
update(v->l, p, x);
}
pull(v);
}
void insert(int p, i64 x) {
if (find(p)) {
update(root, p, x);
} else {
node *l, *r;
split(root, l, r, p);
merge(root, l, new node(p, x));
merge(root, root, r);
}
print();
debug();
}
i64 query(node* v, int l, int r) {
if (r < v->lo || v->hi < l) {
return 0;
} else if (l <= v->lo && v->hi <= r) {
debug("querying treap: ", l, r, v->sum);
return v->sum;
}
i64 ans = ((l <= v->pos && v->pos <= r) ? v->val : 0);
if (v->l) ans = std::gcd(ans, query(v->l, l, r));
if (v->r) ans = std::gcd(ans, query(v->r, l, r));
return ans;
}
i64 query(int l, int r) {
debug("query: ", l, r);
if (!root) {
return 0;
}
return query(root, l, r);
}
void print_vertex(node* v) {
if (!v) {
return;
}
print_vertex(v->l);
debug(v->pos, v->val);
print_vertex(v->r);
}
void print() {
#ifdef DEBUG
debug("treap: ");
print_vertex(root);
#endif
}
};
struct segtree {
int lo, hi;
segtree *l = nullptr, *r = nullptr;
treap tree;
segtree() {}
segtree(int a, int b) : lo(a), hi(b) {}
void fix(int y) {
i64 x = 0;
if (l) x = std::gcd(x, l->tree.query(y, y));
if (r) x = std::gcd(x, r->tree.query(y, y));
tree.insert(y, x);
}
void update(int x, int y, i64 k) {
if (lo == hi) {
tree.insert(y, k);
return;
}
int mid = (lo + hi) >> 1;
if (x <= mid) {
if (!l) {
l = new segtree(lo, mid);
}
l->update(x, y, k);
} else {
if (!r) {
r = new segtree(mid + 1, hi);
}
r->update(x, y, k);
}
fix(y);
}
i64 query(int a, int b, int c, int d) {
if (b < lo || hi < a) {
return 0;
} else if (a <= lo && hi <= b) {
i64 res = tree.query(c, d);
tree.print();
debug("single:", lo, hi, res);
return res;
}
i64 res = 0;
if (l) res = std::gcd(res, l->query(a, b, c, d));
if (r) res = std::gcd(res, r->query(a, b, c, d));
debug(lo, hi, res);
return res;
}
} root;
void init(int R, int C) {
::R = R - 1;
::C = C - 1;
root = segtree(0, R - 1);
}
void update(int P, int Q, i64 K) {
debug("update", P, Q, K);
root.update(P, Q, K);
}
i64 calculate(int P, int Q, int U, int V) {
debug("query", P, Q, U, V);
return root.query(P, U, Q, V);
}
