#include "game.h"
#include <iostream>
#include <numeric>
#include <cmath>
using namespace std;
struct TreapNode
{
int pos;
long long val;
long long totVal;
int priority;
int size;
TreapNode* l;
TreapNode* r;
};
struct Node
{
TreapNode* val;
Node* l;
Node* r;
};
int maxTreapVal;
int segTreeSize;
Node* tree = nullptr;
void recalc(TreapNode* node)
{
node->totVal = gcd(node->val, gcd(node->l ? node->l->totVal : 0, node->r ? node->r->totVal : 0));
node->size = (node->l ? node->l->size : 0) + (node->r ? node->r->size : 0) + 1;
}
TreapNode* rotateL(TreapNode* p)
{
TreapNode* newP = p->r;
p->r = newP->l;
newP->l = p;
recalc(p);
return newP;
}
TreapNode* rotateR(TreapNode* p)
{
TreapNode* newP = p->l;
p->l = newP->r;
newP->r = p;
recalc(p);
return newP;
}
long long queryTreap(TreapNode* node, int l, int r, int ql, int qr)
{
if (!node || qr < l || r < ql)
{
return 0;
}
if (ql <= l && r <= qr)
{
return node->totVal;
}
long long lRes = queryTreap(node->l, l, node->pos - 1, ql, qr);
long long rRes = queryTreap(node->r, node->pos + 1, r, ql, qr);
return gcd(ql <= node->pos && node->pos <= qr ? node->val : 0, gcd(lRes, rRes));
}
TreapNode* insert(TreapNode* node, const TreapNode& upd)
{
if (!node)
{
return new TreapNode{ upd };
}
if (upd.pos == node->pos)
{
node->val = upd.val;
}
else if (upd.pos < node->pos)
{
node->l = insert(node->l, upd);
if (node->priority < node->l->priority)
{
//node = rotateR(node);
}
}
else
{
node->r = insert(node->r, upd);
if (node->priority < node->r->priority)
{
//node = rotateL(node);
}
}
recalc(node);
return node;
}
Node* updateSegtree(Node* node, int l, int r, int i, int j, long long val)
{
if (!node)
{
node = new Node{ nullptr, nullptr, nullptr };
}
node->val = insert(node->val, { j, val, val, rand(), 1, nullptr, nullptr });
if (l == r)
{
return node;
}
int mid = (l + r) / 2;
if (i <= mid)
{
node->l = updateSegtree(node->l, l, mid, i, j, val);
}
else
{
node->r = updateSegtree(node->r, mid + 1, r, i, j, val);
}
return node;
}
long long query(Node* node, int l, int r, int li, int ri, int lj, int rj)
{
if (!node || r < li || ri < l)
{
return 0;
}
if (li <= l && r <= ri)
{
return queryTreap(node->val, 0, maxTreapVal, lj, rj);
}
int mid = (l + r) / 2;
long long lRes = query(node->l, l, mid, li, ri, lj, rj);
long long rRes = query(node->r, mid + 1, r, li, ri, lj, rj);
return gcd(lRes, rRes);
}
void init(int R, int C)
{
segTreeSize = 1 << (int)ceil(log2(R));
maxTreapVal = C - 1;
}
void update(int P, int Q, long long K)
{
tree = updateSegtree(tree, 0, segTreeSize - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return query(tree, 0, segTreeSize - 1, P, U, Q, V);
}
/*int main()
{
init(1e9, 1e9);
update(0, 0, 20);
update(1, 1, 15);
cout << calculate(0, 0, 1, 1) << '\n';
return 0;
}*/
