#pragma GCC optimize("Ofast,unroll-loops,inline")
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = int64_t;
#define int int64_t
#define MAXR 1e9
#define MAXC 1e9
long long gcd2(long long X, long long Y)
{
if (X == 0 || Y == 0)
{
return X + Y;
}
long long tmp;
while (X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct l2_node
{
int ml, mr;
l2_node *lft, *rht;
ll val;
l2_node(int l, int r) : ml(l), mr(r), lft(NULL), rht(NULL), val(1) {}
};
struct l1_node
{
l1_node *lft, *rht;
l2_node l2;
l1_node() : lft(NULL), rht(NULL), l2(0, MAXC) {}
};
static l1_node root;
static void update2(l2_node *node, int q, int k)
{
int tl = node->ml, tr = node->mr;
// Update leaf node
int tm = (tl + tr) >> 1;
if (tl + 1 == tr)
{
node->val = k;
return;
}
l2_node *&curt = (q < tm) ? node->lft : node->rht;
if (curt == NULL)
{
// Make new leaf node, contain the query value
curt = new l2_node(q, q + 1);
curt->val = k;
}
else if (curt->ml <= q && q < curt->mr)
{
// If the node already exist and contain our query point, do update
update2(curt, q, k);
}
else
{
// Travese until the half contain the query node and current node differ;
do
{
(q < tm ? tr : tl) = tm;
tm = (tl + tr) >> 1;
} while ((q < tm) == (curt->ml < tm));
// Make new node and continue to update
l2_node *nnd = new l2_node(tl, tr);
(curt->ml < tm ? nnd->lft : nnd->rht) = curt;
curt = nnd;
update2(nnd, q, k);
}
node->val = gcd2((node->lft ? node->lft->val : 0),
(node->rht ? node->rht->val : 0));
}
ll query2(l2_node *node, int l, int r)
{
if (node == NULL || r <= node->ml || node->mr <= l)
return 0;
else if (l <= node->ml && node->mr <= r)
return node->val;
return gcd2(query2(node->lft, l, r), query2(node->rht, l, r));
}
static void update1(l1_node *node, int l, int r,
int p, int q, int k)
{
int tm = (l + r) >> 1;
if (l + 1 == r)
update2(&node->l2, q, k);
else
{
l1_node *&curt = p < tm ? node->lft : node->rht;
(p < tm ? r : l) = tm;
if (curt == NULL)
curt = new l1_node();
update1(curt, l, r, p, q, k);
k = gcd2((node->lft ? query2(&node->lft->l2, q, q + 1) : 0),
(node->rht ? query2(&node->rht->l2, q, q + 1) : 0));
update2(&node->l2, q, k);
}
}
int query1(l1_node *node, int l, int r, int ax, int ay, int bx, int by)
{
if (node == NULL || ay <= l || r <= ax)
return 0;
else if (ax <= l && r <= ay)
return query2(&node->l2, bx, by);
int tm = (l + r) >> 1;
return gcd2(query1(node->lft, l, tm, ax, ay, bx, by),
query1(node->rht, tm, r, ax, ay, bx, by));
}
#undef int
// Original Function
void init(int R, int C)
{
}
void update(int P, int Q, long long K)
{
update1(&root, 0, MAXR, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return query1(&root, 0, MAXR, P, U + 1, Q, V + 1);
// return 42;
}
