#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef long long ll;
const int N = 300010;
ll rd()
{
ll k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}
return f > 0 ? k : -k;
}
void wr(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
ll gcd(ll a, ll b)
{
if (a < 0)
a = -a;
if (b < 0)
b = -a;
if (a == 0)
return b;
if (b == 0)
return a;
int r = 0;
while (!((a & 1) || (b & 1)))
a >>= 1, b >>= 1, r++;
ll ret = 0;
while (1)
{
while (!(a & 1))
a >>= 1;
while (!(b & 1))
b >>= 1;
if (a > b)
a = a - b;
else
b = b - a;
if (0 == a)
{
ret = b << r;
break;
}
if (0 == b)
{
ret = a << r;
break;
}
}
return ret;
}
struct node
{
node *l, *r;
int pos, key, mn, mx;
ll val, g;
node(int position, ll value)
{
l = r = nullptr;
mn = mx = pos = position;
key = rand();
val = g = value;
}
void pull()
{
g = val;
if (l)
g = gcd(g, l->g);
if (r)
g = gcd(g, r->g);
mn = (l ? l->mn : pos);
mx = (r ? r->mx : pos);
}
};
// memory O(n)
struct treap
{
node *root;
treap()
{
root = nullptr;
}
void split(node *t, int pos, node *&l, node *&r)
{
if (t == nullptr)
{
l = r = nullptr;
return;
}
if (t->pos < pos)
{
split(t->r, pos, l, r);
t->r = l;
l = t;
}
else
{
split(t->l, pos, l, r);
t->l = r;
r = t;
}
t->pull();
}
node *merge(node *l, node *r)
{
if (!l || !r)
return l ? l : r;
if (l->key < r->key)
{
l->r = merge(l->r, r);
l->pull();
return l;
}
r->l = merge(l, r->l);
r->pull();
return r;
}
bool find(int pos)
{
node *t = root;
while (t)
{
if (t->pos == pos)
return true;
if (t->pos > pos)
t = t->l;
else
t = t->r;
}
return false;
}
void upd(node *t, int pos, ll val)
{
if (t->pos == pos)
{
t->val = val;
t->pull();
return;
}
if (t->pos > pos)
upd(t->l, pos, val);
else
upd(t->r, pos, val);
t->pull();
}
void insert(int pos, ll val)
{ // set a_pos = val
if (find(pos))
upd(root, pos, val);
else
{
node *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new node(pos, val)), r);
}
}
ll query(node *t, int st, int en)
{
if (t->mx < st || en < t->mn)
return 0;
if (st <= t->mn && t->mx <= en)
return t->g;
ll ans = (st <= t->pos && t->pos <= en ? t->val : 0);
if (t->l)
ans = gcd(ans, query(t->l, st, en));
if (t->r)
ans = gcd(ans, query(t->r, st, en));
return ans;
}
ll query(int l, int r)
{ // gcd of a_i such that l <= i <= r
if (!root)
return 0;
return query(root, l, r);
}
void print(node *t)
{
if (!t)
return;
print(t->l);
wr(t->val), putchar('\n');
print(t->r);
}
};
// Dynamic 2D Query Tree From Shahjalal Shohag
// total memory along with treap = nlogn
struct ST
{
ST *l, *r;
treap t;
int b, e;
ST()
{
l = r = nullptr;
}
ST(int st, int en)
{
l = r = nullptr;
b = st, e = en;
}
void fix(int pos)
{
ll val = 0;
if (l)
val = gcd(val, l->t.query(pos, pos));
if (r)
val = gcd(val, r->t.query(pos, pos));
t.insert(pos, val);
}
void upd(int x, int y, ll val)
{ // set a[x][y] = val
if (e < x || x < b)
return;
if (b == e)
{
t.insert(y, val);
return;
}
if (b != e)
{
if (x <= (b + e) / 2)
{
if (!l)
l = new ST(b, (b + e) / 2);
l->upd(x, y, val);
}
else
{
if (!r)
r = new ST((b + e) / 2 + 1, e);
r->upd(x, y, val);
}
}
fix(y);
}
// gcd of a[x][y] such that i <= x <= j && st <= y <= en
ll query(int i, int j, int st, int en)
{
if (e < i || j < b)
return 0;
if (i <= b && e <= j)
return t.query(st, en);
ll ans = 0;
if (l)
ans = gcd(ans, l->query(i, j, st, en));
if (r)
ans = gcd(ans, r->query(i, j, st, en));
return ans;
}
};
ST t;
void init(int R, int C)
{
srand(time(NULL));
t = ST(0, R - 1);
}
void update(int P, int Q, long long K)
{
t.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return t.query(P, U, Q, V);
}
void test_interaction()
{
int n = rd(), m = rd();
init(n, m);
int q = rd();
while(q--)
{
int op = rd();
//op 1 : update single point
if (op == 1)
{
int x = rd(), y = rd(); ll w = rd();
update(x, y, w);
}
//op 2 : 2D gcd query
else
{
int xl = rd(), yl = rd(), xr = rd(), yr = rd();
wr(calculate(xl, xr, yl, yr)), putchar('\n');
}
}
}
Compilation message
/usr/bin/ld: /tmp/cc6UC25A.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
