#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>
#include <unordered_map>
#include <cassert>
#include "game.h"
std::mt19937 rng(53);
/*long long std::__gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}*/
namespace Treap {
struct Node {
std::pair<int,int> p;
int64_t val; // y, x
int64_t gcd;
int size;
int prio;
Node* l;
Node* r;
Node(std::pair<int,int> p, int64_t val):
p(p), val(val), gcd(val), size(1), prio(rng()), l(nullptr), r(nullptr) {}
~Node() {
if (l) {
delete l;
}
if (r) {
delete r;
}
}
};
Node* _aux_split_l = nullptr;
Node* _aux_split_r = nullptr;
Node* _aux_merge = nullptr;
int GetNodeSize(Node* node) {
if (!node) {
return 0;
}
return node->size;
}
int64_t GetNodeGCD(Node* node) {
if (!node) {
return 0;
}
return node->gcd;
}
void NodeUpdate(Node* node) {
if (!node) {
return;
}
node->size = 1;
node->gcd = node->val;
if (node->l) {
node->size += node->l->size;
node->gcd = std::__gcd(node->gcd, node->l->gcd);
}
if (node->r) {
node->size += node->r->size;
node->gcd = std::__gcd(node->gcd, node->r->gcd);
}
}
// l < key, r >= key
void SplitDriver(Node* node, int key) {
if (!node) {
_aux_split_l = _aux_split_r = nullptr;
return;
}
int node_key = GetNodeSize(node->l);
if (key-node_key-1>=0) {
SplitDriver(node->r,key-node_key-1);
node->r = _aux_split_l;
_aux_split_l = node;
NodeUpdate(node);
}
else {
SplitDriver(node->l,key);
node->l = _aux_split_r;
_aux_split_r = node;
NodeUpdate(node);
}
}
std::pair<Node*, Node*> Split(Node* node, int key) {
SplitDriver(node,key);
return {_aux_split_l, _aux_split_r};
}
void MergeDriver(Node* a, Node* b) {
if (!a) {
_aux_merge = b;
return;
}
if (!b) {
_aux_merge = a;
return;
}
if (a->prio > b->prio) {
MergeDriver(a->r,b);
a->r = _aux_merge;
_aux_merge = a;
NodeUpdate(a);
}
else {
MergeDriver(a,b->l);
b->l = _aux_merge;
_aux_merge = b;
NodeUpdate(b);
}
}
Node* Merge(Node* a, Node* b) {
MergeDriver(a,b);
return _aux_merge;
}
Node* Insert(Node*& root, int pos, std::pair<int,int> p, int64_t val) {
if (!root) {
return root = new Node(p, val);
}
auto trees = Split(root,pos);
return root = Merge(Merge(trees.first, new Node(p, val)), trees.second);
}
Node* Remove(Node*& root, int pos) {
if (!root) {
return root;
}
auto trees = Split(root,pos);
auto trees_right = Split(trees.second,1);
delete trees_right.first;
return root = Merge(trees.first,trees_right.second);
}
int LowerBound(Node* node, std::pair<int,int> p, int skipped = 0, int depth = 0) {
if (!node) {
return 0x3f3f3f3f;
}
int node_key = skipped + GetNodeSize(node->l);
if (node->p >= p) {
return std::min(node_key, LowerBound(node->l, p, skipped, 1));
}
else {
return LowerBound(node->r, p, node_key+1, 1);
}
}
int UpperBound(Node* node, std::pair<int,int> p, int skipped = 0, int depth = 0) {
if (!node) {
return -1;
}
int node_key = skipped + GetNodeSize(node->l);
if (node->p <= p) {
return std::max(node_key, UpperBound(node->r, p, node_key+1));
}
else {
return UpperBound(node->l, p, skipped);
}
}
int64_t RangeGCDQuery(Node*& root, int l, int r) {
if (!root) {
return 0;
}
auto trees = Split(root,l);
auto trees_right = Split(trees.second,r-l+1);
int64_t ret = GetNodeGCD(trees_right.first);
root = Merge(Merge(trees.first,trees_right.first),trees_right.second);
return ret;
}
std::pair<int,int> GetKth(Node*& node, int k, int skipped = 0) {
//std::cout << Treap::GetNodeSize(node) << " " << k << "\n";
if (!node) {
return {-1, -1};
}
int node_key = skipped + GetNodeSize(node->l);
if (node_key==k) {
return node->p;
}
else if (node_key>k) {
return GetKth(node->l,k,skipped);
}
else {
return GetKth(node->r,k,node_key+1);
}
/*auto trees = Split(node,k);
auto trees_right = Split(trees.second,1);
auto ret = trees_right.first->p;
node = Merge(Merge(trees.first,trees_right.first),trees_right.second);
return ret;*/
}
};
struct SegTreeNode {
Treap::Node* treap = nullptr;
SegTreeNode* l = nullptr;
SegTreeNode* r = nullptr;
~SegTreeNode() {
if (l) {
delete l;
}
if (r) {
delete r;
}
}
};
int r, c;
SegTreeNode* root = nullptr;
std::unordered_map<int, std::unordered_map<int, int64_t>> arr;
void Insert(SegTreeNode* node, int l, int r, int x, int y, int64_t val) {
std::pair<int,int> p(y,x);
int pos = Treap::LowerBound(node->treap, p);
if (pos==0x3f3f3f3f) {
pos = Treap::GetNodeSize(node->treap);
}
node->treap = Treap::Insert(node->treap, pos, p, val);
if (l==r) {
return;
}
int m = (l+r)>>1;
if (x<=m) {
if (!node->l) {
node->l = new SegTreeNode;
}
Insert(node->l,l,m,x,y,val);
}
else {
if (!node->r) {
node->r = new SegTreeNode;
}
Insert(node->r,m+1,r,x,y,val);
}
}
void Remove(SegTreeNode* node, int l, int r, int x, int y) {
std::pair<int,int> p(y,x);
int pos = Treap::LowerBound(node->treap, p);
assert(pos != 0x3f3f3f3f);
node->treap = Treap::Remove(node->treap, pos);
if (l==r) {
return;
}
int m = (l+r)>>1;
if (x<=m) {
Remove(node->l,l,m,x,y);
}
else {
Remove(node->r,m+1,r,x,y);
}
}
int64_t Query(SegTreeNode* node, int l, int r, int st, int fi, int a, int b) {
if (!node) {
return 0;
}
if (l>fi||r<st) {
return 0;
}
if (st<=l&&r<=fi) {
std::pair<int,int> pl(a,-1);
std::pair<int,int> pr(b+1,-1);
int le = Treap::LowerBound(node->treap, pl);
int ri = Treap::UpperBound(node->treap, pr);
if (le==0x3f3f3f3f) {
le = Treap::GetNodeSize(node->treap);
}
if (le==0x3f3f3f3f||ri==-1||le>ri) {
return 0;
}
else {
return Treap::RangeGCDQuery(node->treap, le, ri);
}
}
int m = (l+r)>>1;
return std::__gcd(Query(node->l,l,m,st,fi,a,b), Query(node->r,m+1,r,st,fi,a,b));
}
void init(int R, int C) {
r = R;
c = C;
root = new SegTreeNode;
}
void update(int P, int Q, long long K) {
if (arr[P].count(Q)) {
arr[P].erase(Q);
Remove(root, 0, r-1, P, Q);
}
arr[P][Q] = K;
Insert(root, 0, r-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return Query(root, 0, r-1, P, U, Q, V);
}
