#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifndef local
#include "game.h"
#endif // local
using namespace std;
using ll = long long;
const int N = 22000, LG = 30;
inline ll gcd(ll a, ll b) {
if(!a || !b) return a | b;
int s = __builtin_ctzll(a | b);
a >>= s, b >>= s;
while(a && b) {
a >>= __builtin_ctzll(a);
b >>= __builtin_ctzll(b);
if(a > b) a -= b;
else if(b > a) b -= a;
else return a << s;
}
return (a | b) << s;
}
int R, C;
class Treap {
private:
struct node {
int key, pri;
ll val, ans;
node *l, *r;
node(int k, ll v) : key(k), pri(rand()), val(v), ans(v), l(0), r(0) {}
void pull() {
ans = gcd(val, gcd(l ? l->ans : 0, r ? r->ans : 0));
sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
}
} *root;
void split(int k, node *o, node *&a, node *&b) {
// a: key < k, b: key >= k
if(!o) return a = b = nullptr, void();
if(o->key < k)
a = o, split(k, o->r, a->r, b), a->pull();
else
b = o, split(k, o->l, a, b->l), b->pull();
}
node *join(node *a, node *b) {
if(!a || !b) return a ? a : b;
if(a->pri < b->pri)
return a->r = join(a->r, b), a->pull(), a;
else
return b->l = join(a, b->l), b->pull(), b;
}
public:
Treap() : root(nullptr) {}
void modify(int p, ll v) {
node *a, *b, *c;
split(p, root, a, b);
split(p+1, b, b, c);
if(b == nullptr)
b = new node(p, v);
else
b->val = b->ans = v;
root = join(a, join(b, c));
}
ll query(int l, int r) {
node *a, *b, *c;
split(l, root, a, b);
split(r, b, b, c);
ll res = b ? b->ans : 0;
root = join(a, join(b, c));
return res;
}
};
struct Segtree2d {
struct node {
Treap st;
node *l, *r;
node() : l(nullptr), r(nullptr) {}
// Complexity of pull would TLE
// Notice that only posy would change
void pull(int y) {
st.modify(y, gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
}
} *root;
void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
if(!cur) cur = new node();
if(l+1 == r) {
cur->st.modify(posy, v);
return;
}
int m = l+(r-l)/2;
if(posx < m)
modify(posx, posy, v, cur->l, l, m);
else
modify(posx, posy, v, cur->r, m, r);
cur->pull(posy);
}
ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
if(r <= lx || l >= rx || !cur) return 0;
if(lx <= l && r <= rx) return cur->st.query(ly, ry);
int m = l+(r-l)/2;
return gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
}
Segtree2d() : root(nullptr) {}
void modify(int posx, int posy, ll v) {
modify(posx, posy, v, root, 0, R);
}
ll query(int lx, int rx, int ly, int ry) {
return query(lx, rx, ly, ry, root, 0, R);
}
} sgt;
void init(int r, int c) {
R = r, C = c;
}
void update(int x, int y, ll k) {
sgt.modify(x, y, k);
}
ll calculate(int lx, int ly, int rx, int ry) {
if(lx > rx) swap(lx, rx);
if(ly > ry) swap(ly, ry);
return sgt.query(lx, rx+1, ly, ry+1);
}
#ifdef local
signed main() {
int a, b, n;
cin >> a >> b >> n;
init(a, b);
for(int i = 0; i < n; i++) {
int t;
cin >> t;
if(t == 1) {
int x, y;
ll k;
cin >> x >> y >> k;
update(x, y, k);
} else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << calculate(x1, y1, x2, y2) << '\n';
}
}
}
#endif // local
Compilation message
game.cpp:2: warning: ignoring #pragma loop_opt [-Wunknown-pragmas]
2 | #pragma loop_opt(on)
|
game.cpp: In member function 'void Treap::node::pull()':
game.cpp:37:13: error: 'sz' was not declared in this scope
37 | sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
| ^~
game.cpp:37:30: error: 'struct Treap::node' has no member named 'sz'
37 | sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
| ^~
game.cpp:37:48: error: 'struct Treap::node' has no member named 'sz'
37 | sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
| ^~
