#include <bits/stdc++.h>
#include "game.h"
#define f first
#define s second
#define pll pair<ll, ll>
#define ll long long
using namespace std;
mt19937 rnd(time(NULL));
ll R, C;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Treap {
struct node {
ll val, gcd, sz, pri;
pll pos;
node *l, *r;
node(ll val=0, pll pos={0, 0}, node *l=NULL, node *r=NULL) :
val(val), gcd(val), sz(1), pri(rnd()), pos(pos), l(l), r(r) {}
};
node *root;
Treap() : root(NULL) {}
void recalc(node *cur) {
if (cur == NULL) return;
cur->sz = 1;
cur->gcd = cur->val;
if (cur->l != NULL)
cur->sz += cur->l->sz, cur->gcd = gcd2(cur->gcd, cur->l->gcd);
if (cur->r != NULL)
cur->sz += cur->r->sz, cur->gcd = gcd2(cur->gcd, cur->r->gcd);
}
void split(node *cur, node *&left, node *&right, pll pos) {
if (cur == NULL) {
left = right = NULL;
return;
}
if (cur->pos <= pos) {
split(cur->r, cur->r, right, pos);
left = cur;
} else {
split(cur->l, left, cur->l, pos);
right = cur;
}
recalc(cur);
}
void merge(node *&cur, node *left, node *right) {
if (left == NULL || right == NULL) {
cur = (left != NULL ? left : right);
return;
}
if (left->pri >= right->pri) {
merge(left->r, left->r, right);
cur = left;
} else {
merge(right->l, left, right->l);
cur = right;
}
recalc(cur);
}
void update(ll x, ll y, ll val) {
node *left, *mid, *right;
split(root, left, mid, {y, x-1});
split(mid, mid, right, {y, x});
delete mid;
merge(root, left, new node(val, {y, x}));
merge(root, root, right);
}
ll gcd_range(ll yl, ll yr) {
node *left, *mid, *right;
split(root, left, mid, {yl, -1});
split(mid, mid, right, {yr+1, -1});
ll ans = (mid != NULL ? mid->gcd : 0);
merge(root, left, mid);
merge(root, root, right);
return ans;
}
};
struct Segtree {
struct node {
Treap treap;
node *l, *r;
node() :
treap(Treap()), l(NULL), r(NULL) {}
};
node *root;
void update(ll x, ll y, ll val, node *&cur, ll l, ll r) {
if (cur == NULL) cur = new node();
cur->treap.update(x, y, val);
if (l == r) return;
ll mid = (l + r) >> 1;
if (x <= mid) update(x, y, val, cur->l, l, mid);
else update(x, y, val, cur->r, mid+1, r);
}
ll gcd_range(ll xl, ll yl, ll xr, ll yr, node *cur, ll l, ll r) {
if (cur == NULL) return 0;
if (xr < l || r < xl) return 0;
if (xl <= l && r <= xr) {
return cur->treap.gcd_range(yl, yr);
}
ll mid = (l + r) >> 1;
ll resl = gcd_range(xl, yl, xr, yr, cur->l, l, mid);
ll resr = gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);
return gcd2(resl, resr);
// if (xl == l && r == xr) {
// return cur->treap.gcd_range(yl, yr);
// }
// ll mid = (l + r) >> 1;
// if (xr <= mid) {
// return gcd_range(xl, yl, xr, yr, cur->l, l, mid);
// } else if (xl >= mid + 1) {
// return gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);
// } else {
// return gcd2(
// gcd_range(xl, yl, mid, yr, cur->l, l, mid),
// gcd_range(mid+1, yl, xr, yr, cur->r, mid+1, r)
// );
// }
}
} segtree;
void init(int R, int C) {
::R = R;
::C = C;
}
void update(int x, int y, ll val) {
x++, y++;
segtree.update(x, y, val, segtree.root, 1, R);
}
ll calculate(int xl, int yl, int xr, int yr) {
xl++, yl++, xr++, yr++;
return segtree.gcd_range(xl, yl, xr, yr, segtree.root, 1, R);
}
