#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
struct Node {
ll val;
int lef, rig;
} a[maxn * 140];
#define lef(x) (a[x].lef)
#define rig(x) (a[x].rig)
#define val(x) (a[x].val)
#define Node int&
void comb(int x) {
val(x) = gcd(val(lef(x)), val(rig(x)));
}
int new_node(ll v) {
static int sz = 0;
++sz;
return sz;
}
int root2d, R, C;
unordered_map<int, int> root;
void set1d(int l, int r, Node x, Node r1, Node r2, int k, ll v) {
if (!x) x = new_node(0);
if (l == r) {
if (!r1 & !r2) {
val(x) = v;
} else {
val(x) = gcd(val(r1), val(r2));
}
} else {
int m = (l + r) >> 1;
if (k <= m) set1d(l, m, lef(x), lef(r1), lef(r2), k, v);
else set1d(m + 1, r, rig(x), rig(r1), rig(r2), k, v);
comb(x);
}
}
void set2d(int l, int r, Node x, int _x, int _y, ll v) {
if (!x) x = new_node(0);
if (l != r) {
int m = (l + r) >> 1;
if (_x <= m) set2d(l, m, lef(x), _x, _y, v);
else set2d(m + 1, r, rig(x), _x, _y, v);
}
set1d(0, C - 1, root[x], root[lef(x)], root[rig(x)], _y, v);
}
ll qry1d(int l, int r, Node x, int L, int R) {
// printf("qry1d %d %d %d\n", l, r, x);
if (!x) return 0;
if (l > R || r < L) return 0;
if (l >= L && r <= R) return val(x);
int m = (l + r) >> 1;
return gcd(qry1d(l, m, lef(x), L, R), qry1d(m + 1, r, rig(x), L, R));
}
ll qry2d(int l, int r, Node x, int L, int R, int _L, int _R) {
if (!x) return 0;
if (l > R || r < L) return 0;
// printf("qry2d %d %d %d %d %d\n", l, r, L, R, x);
if (l >= L && r <= R) return qry1d(0, C - 1, root[x], _L, _R);
int m = (l + r) >> 1;
return gcd(qry2d(l, m, lef(x), L, R, _L, _R), qry2d(m + 1, r, rig(x), L, R, _L, _R));
}
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void init(int R, int C) {
/* ... */
}
void update(int P, int Q, long long K) {
set2d(0, R - 1, root2d, P, Q, v);
}
long long calculate(int P, int Q, int U, int V) {
if (P > U) swap(P, U);
if (Q > V) swap(Q, V);
return qry2d(0, R - 1, root2d, P, U, Q, V);
}
/*
signed main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(false);
int m;
cin >> R >> C >> m;
// printf("%d %d %d\n", R, C, m);
while (m--) {
int op;
cin >> op;
// printf("%d\n", op);
if (op == 1) {
int x, y;
ll v;
cin >> x >> y >> v;
modify(x, y, v);
} else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
ll res = qry(x1, x2, y1, y2);
cout << res << "\n";
}
}
// printf("%d %d\n", root2d, root[root2d]);
}*/
/*
1 1 64
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 5352072091165800
2 0 0 0 0
1 0 0 15571253006461152
1 0 0 36204425277916896
1 0 0 80686018200191040
1 0 0 720602986354563312
2 0 0 0 0
1 0 0 90705271009665312
2 0 0 0 0
1 0 0 583803309300971760
1 0 0 3317329660750560
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 84776821924066272
1 0 0 581927323100969664
1 0 0 93139161501610224
1 0 0 28340661117472704
1 0 0 74529074218959360
2 0 0 0 0
1 0 0 462419028676725120
1 0 0 4416867915235776
1 0 0 840475934823549024
1 0 0 8247617084266560
1 0 0 117571055091706944
1 0 0 839204903894797440
1 0 0 820805176764813240
1 0 0 82688722861897152
1 0 0 136422472061715840
1 0 0 555837014267982720
1 0 0 935087613488388360
1 0 0 17770822018565616
1 0 0 10726679222715456
1 0 0 621229604181863040
1 0 0 12477973789689408
2 0 0 0 0
1 0 0 227153207069268480
1 0 0 262037449583477568
1 0 0 562837835495871936
1 0 0 131875056326325312
1 0 0 922430858108760
1 0 0 763487168205041280
2 0 0 0 0
2 0 0 0 0
1 0 0 551850903114166656
1 0 0 243713152409807808
1 0 0 306811355534716032
1 0 0 115604757169181280
2 0 0 0 0
1 0 0 29254579698314880
1 0 0 35080064244441216
1 0 0 97819409912384160
1 0 0 34259332503876480
2 0 0 0 0
2 0 0 0 0
1 0 0 159548730492191040
1 0 0 11555364984947784
2 0 0 0 0
1 0 0 3373083100427040
2 0 0 0 0
2 0 0 0 0*/
Compilation message
game.cpp: In function 'void comb(int)':
game.cpp:15:14: error: 'gcd' was not declared in this scope
15 | val(x) = gcd(val(lef(x)), val(rig(x)));
| ^~~
game.cpp: In function 'void set1d(int, int, int&, int&, int&, int, ll)':
game.cpp:31:22: error: 'gcd' was not declared in this scope
31 | val(x) = gcd(val(r1), val(r2));
| ^~~
game.cpp: In function 'll qry1d(int, int, int&, int, int)':
game.cpp:56:12: error: 'gcd' was not declared in this scope
56 | return gcd(qry1d(l, m, lef(x), L, R), qry1d(m + 1, r, rig(x), L, R));
| ^~~
game.cpp: In function 'll qry2d(int, int, int&, int, int, int, int)':
game.cpp:64:12: error: 'gcd' was not declared in this scope
64 | return gcd(qry2d(l, m, lef(x), L, R, _L, _R), qry2d(m + 1, r, rig(x), L, R, _L, _R));
| ^~~
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:83:35: error: 'v' was not declared in this scope
83 | set2d(0, R - 1, root2d, P, Q, v);
| ^
