/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include "game.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
long long gcd2(long long X, long long Y) {
if(X == 0) return Y;
if(Y == 0) return X;
long long tmp;
while (X != Y && Y != 0) {
tmp = X; X = Y;
Y = tmp % Y;
}
return X;
}
/*
Naively, inserting N elements into a sparse segment tree requires O(N log C) memory, giving a bound of O(N log^2C) on 2D segment tree memory.
This is usually too much for N=C=10^5 and 256 MB
Possible ways to get around this:
- Use arrays of fixed size rather than pointers.
- Reduce the memory usage of sparse segment tree to $O(N)$ while maintaining the same O(N\log C) insertion time
(see the solution for IOI Game below for details).
- Use BBSTs instead of sparse segment trees: https://cp-algorithms.com/data_structures/treap.html
*/
/// 2D segment tree with Treap on Y to reduce memory
struct NODEY {
int key, priority;
long long val, ans;
NODEY *l, *r;
NODEY(int _key, long long _val) : key(_key), priority(rand() + (rand() << 15)), val(_val), ans(_val), l(NULL), r(NULL) {}
};
typedef NODEY* pNODEY;
int NYseg[2];
long long ans(pNODEY t) { return t ? t->ans : 0; }
void pullY(pNODEY t) {
if (t) t->ans = gcd2(gcd2(ans(t->l), ans(t->r)), t->val);
}
void splitY(pNODEY t, int key, pNODEY &l, pNODEY &r) {
if (!t)
l = r = NULL;
else if (key < t->key)
splitY(t->l, key, l, t->l), r = t;
else
splitY(t->r, key, t->r, r), l = t;
pullY(t);
}
void mergeY(pNODEY &t, pNODEY l, pNODEY r) {
if (!l || !r)
t = l ? l : r;
else if (l->priority > r->priority)
mergeY(l->r, l->r, r), t = l;
else
mergeY(r->l, l, r->l), t = r;
pullY(t);
}
long long queY(int l, int r, pNODEY t) { // [l, r]
pNODEY pl, pm, pr;
splitY(t, l-1, pl, pm); splitY(pm, r, t, pr);
long long ret = ans(t);
mergeY(pm, pl, t); mergeY(t, pm, pr);
return ret;
}
void updY(int p, long long val, pNODEY &t) {
pNODEY pl, pm, pr;
splitY(t, p-1, pl, pm); splitY(pm, p, t, pr);
if (t) t->val = t->ans = val;
else t = new NODEY(p, val);
mergeY(pm, pl, t); mergeY(t, pm, pr);
}
struct NODEX {
NODEX *lp, *rp; // left ptr, right ptr
pNODEY pny;
NODEX() : lp(NULL), rp(NULL), pny(NULL) {}
};
NODEX nx;
int NXseg[2];
void pullX(int vty, NODEX *pnx) {
ll g1 = (!pnx->lp) ? 0LL : queY(vty, vty, pnx->lp->pny);
ll g2 = (!pnx->rp) ? 0LL : queY(vty, vty, pnx->rp->pny);
ll g0 = gcd2(g1, g2);
updY(vty, g0, pnx->pny);
}
void updX(int vtx, int vty, ll val, NODEX *pnx, int l = NXseg[0], int r = NXseg[1]){
if(l == r) { updY(vty, val, pnx->pny); return; } // leaf
int mid = (l + r) / 2;
if (vtx <= mid) {
if(!pnx->lp) pnx->lp = new NODEX();
updX(vtx, vty, val, pnx->lp, l, mid);
} else {
if(!pnx->rp) pnx->rp = new NODEX();
updX(vtx, vty, val, pnx->rp, mid+1, r);
}
pullX(vty, pnx);
}
ll queX(int qxle, int qxri, int qyle, int qyri, NODEX *pnx, int l = NXseg[0], int r = NXseg[1]) { // [l, r]
if(r < qxle || l > qxri) return 0LL;
if(qxle <= l && r <= qxri) return queY(qyle, qyri, pnx->pny);
int mid = (l + r) / 2;
ll g1 = (!pnx->lp) ? 0LL : queX(qxle, qxri, qyle, qyri, pnx->lp, l, mid);
ll g2 = (!pnx->rp) ? 0LL : queX(qxle, qxri, qyle, qyri, pnx->rp, mid+1, r);
return gcd2(g1, g2);
}
void init(int R, int C) {
NXseg[0] = 0; NXseg[1] = C - 1;
NYseg[0] = 0; NYseg[1] = R - 1;
}
void update(int P, int Q, long long K) {
updX(Q, P, K, &nx);
}
long long calculate(int y10, int x10, int y20, int x20) {
int x1 = min(x10, x20), x2 = max(x10, x20);
int y1 = min(y10, y20), y2 = max(y10, y20);
return queX(x1, x2, y1, y2, &nx);
}
