#include <bits/stdc++.h>
//#include "game.h"
using namespace std;
#define int long long
#define ar array
const int INF = 1e18;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Teapy{
struct Node{
int h;
ar<int, 2> b;
Node *l, *r;
int val;
int g;
Node(ar<int, 2> ind, int v){
val = v;
g = v;
b = ind;
h = rand();
l = r = nullptr;
};
void merge(){
g = val;
if (l) g = gcd2(g, l->g);
if (r) g = gcd2(g, r->g);
}
};
Node* root;
Teapy(){
root = nullptr;
}
void split(Node* k, Node* &l, Node* &r, ar<int, 2> val){
if (!k) return;
if (k->b <= val){
l = k;
Node* tmp = nullptr;
split(k->r, tmp, r, val);
l->r = tmp;
}
else{
r = k;
Node* tmp = nullptr;
split(k->l, l, tmp, val);
r->l = tmp;
}
if (l) l->merge();
if (r) r->merge();
}
void merge(Node* L, Node* R, Node* &res){
if (!L){
res = R;
return;
}
if (!R){
res = L;
return;
}
if (L->h > R->h){
Node* tmp = nullptr;;
merge(L->r, R, tmp);
L->r = tmp;
res = L;
}
else{
Node* tmp = nullptr;
merge(L, R->l, tmp);
R->l = tmp;
res = R;
}
if (res) res->merge();
}
int qry(int l, int r){
Node* a = nullptr;
Node* b = nullptr;
Node* c = nullptr;
Node* d = nullptr;
split(root, a, b, {l - 1, INF});
split(b, c, d, {r, INF});
int ans = 0;
if (c) ans = c->g;
Node* tmp;
merge(a, c, tmp);
Node* tmp2;
merge(tmp, d, root);
return ans;
}
void upd(ar<int, 2> ind, int val){
Node* a = nullptr;
Node* b = nullptr;
Node* c = nullptr;
Node* d = nullptr;
split(root, a, b, {ind[0], ind[1] - 1});
split(b, c, d, ind);
if (!c) c = new Node(ind, val);
c->val = val;
c->g = val;
Node* tmp = nullptr;
merge(a, c, tmp);
merge(tmp, d, root);
}
};
struct Seggy{
struct Node{
Node *l, *r;
Teapy *t;
Node(){
t = new Teapy();
l = r = nullptr;
}
};
int n;
Node* root;
Seggy(){
root = new Node();
}
Seggy(int _n){
root = new Node();
n = _n;
srand(time(nullptr));
}
void upd(Node* k, int tl, int tr, int x, int y, int v){
k->t->upd({y, x}, v);
if (tl == tr) return;
int tm = (tl + tr) / 2;
if (x <= tm){
if (!k->l) k->l = new Node();
upd(k->l, tl, tm, x, y, v);
}
else{
if (!k->r) k ->r = new Node();
upd(k->r, tm + 1, tr, x, y, v);
}
}
int qry(Node* k, int tl, int tr, int l, int r, ar<int, 2> v){
if (l > tr || tl > r) return 0;
if (l <= tl && tr <= r) return k->t->qry(v[0], v[1]);
int mid = (tl + tr) / 2;
int ans = 0;
if (l <= mid && k->l)ans = gcd2(ans, qry(k->l, tl, mid, l, r, v));
if (r > mid && k->r)ans = gcd2(ans, qry(k->r, mid + 1, tr, l, r, v));
return ans;
}
void upd(int sx, int sy, int val){
upd(root, 0, n - 1, sx, sy, val);
}
int qry(int a, int b, int c, int d){
return qry(root, 0, n - 1, a, b, {c, d});
}
};
Seggy s;
void init(signed R, signed C) {
s = Seggy(R);
}
void upd(signed P, signed Q, long long K) {
s.upd(P, Q , K);
}
long long calculate(signed P, signed Q, signed U, signed V) {
return s.qry(P, U, Q, V);
}
Compilation message
game.cpp: In member function 'long long int Teapy::qry(long long int, long long int)':
game.cpp:104:15: warning: unused variable 'tmp2' [-Wunused-variable]
104 | Node* tmp2;
| ^~~~
/usr/bin/ld: /tmp/ccI7E4lh.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status
