game.cpp

// Game - IOI'13
// Complexidade: O(n* log n)
// Thiago Mota

%:include <bits/stdc++.h>
%:define gc getchar_unlocked
using namespace std;random_device rd;mt19937 gen(rd());typedef long long ll;const int INF = 0x3f3f3f3f;typedef pair<int, int> pii;int N, M;ll mdc(ll a, ll b) <% return (b==0?a:mdc(b, a%b)); ??>inline int scan()<%	int N=0, x=gc(), s=1;	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;	for(;x>='0'&&x<='9';x=gc()) N = (N<<3) + (N<<1) + x-'0';	return N;??>struct Node<%	ll v, gcd;	int w;	pii key, ini, fim;	Node *l, *r;	Node(pii key, ll v): key(key), v(v), ini(key), fim(key), w(gen()), gcd(v), l(0), r(0) <%  ??>??>;inline ll gcd(Node *t) <% return (t?t->gcd:0); ??>inline void update(Node*& t)<%	if(!t) return;	t->gcd = mdc(t->v, mdc(gcd(t->l), gcd(t->r)));	t->ini = (t->l ? t->l->ini : t->key);	t->fim = (t->r ? t->r->fim : t->key);??>void merge(Node*& t, Node *l, Node *r)<%	if(!l || !r) return void(t=(l?l:r));	if(l->w >= r->w)<%		merge(l->r, l->r, r);		t = l;	??>else<%		merge(r->l, l, r->l);		t = r;	??>	update(t);??>void split(Node *t, Node*& l, Node*& r, pii key)<%	if(!t) return void(l=r=0);	if(t->key < key)<%		split(t->r, t->r, r, key);		l = t;	??>else<%		split(t->l, l, t->l, key);		r = t;	??>	update(t);??>void fast_insert(Node*& t, Node *it)<%	if(!t) t=it;	else if(it->w >= t->w) split(t, it->l, it->r, it->key), t=it;	else if(it->key < t->key) fast_insert(t->l, it);	else fast_insert(t->r, it);	update(t);??>bool find(Node*& t, pii key, ll val)<%	if(!t) return 0;	if(t->key == key)<%		t->v = val;		update(t);		return 1;	??>	bool x = find(key<t->key?t->l:t->r,key,val);	if(x) update(t);	return x;??>inline void insert(Node*& t, pii key, ll val)<%	if(find(t, key, val)) return;	Node *aux = new Node(key, val);	fast_insert(t, aux);??>ll fast_query(Node*& t, pii i, pii j)<%	if(!t) return 0;	if(i <= t->ini && t->fim <= j) return t->gcd;	else if(j < t->key) return fast_query(t->l, i, j);	else if(i > t->key) return fast_query(t->r, i, j);	return mdc(t->v, mdc(fast_query(t->l, i, j), fast_query(t->r, i, j)));??>ll query(Node*& t, int i, int j)<%	return fast_query(t, pii(i, -INF), pii(j, INF));??>ostream& operator<<(ostream& out, Node *t)<%	if(!t) return out;	out << t->l << t->v << " " << t->r;	return out;??>struct Seg<%	Node *treap;	Seg *l, *r;	Seg(): treap(0), l(0), r(0) <%  ??>	void update_seg(int l1, int c1, ll val, int ini=1, int fim=N)<%		if(ini == fim)<%			insert(treap, pii(c1, l1), val);			return;		??>		insert(treap, pii(c1, l1), val);		int meio = (ini+fim)/2;		if(ini <= l1 && l1 <= meio)<%			if(!l) l = new Seg;			l->update_seg(l1, c1, val, ini, meio);		??>else<%			if(!r) r = new Seg;			r->update_seg(l1, c1, val, meio+1, fim);		??>	??>	ll query_seg(int l1, int c1, int l2, int c2, int ini=1, int fim=N)<%		if(l1 <= ini && fim <= l2) return query(treap, c1, c2);		int meio = (ini + fim) / 2;		if(l1 > meio) return (r?r->query_seg(l1, c1, l2, c2, meio+1, fim):0);		else if(l2 <= meio) return (l?l->query_seg(l1, c1, l2, c2, ini, meio):0);		ll aux = (r?r->query_seg(l1, c1, l2, c2, meio+1, fim):0);		if(aux==1) return 1;		return mdc((l?l->query_seg(l1, c1, l2, c2, ini, meio):0), aux);	??>??>;Seg *no;void init(int R, int C)<%	no = new Seg;	N=R;	M=C;??>void update(int P, int Q, ll K)<%	no->update_seg(P+1, Q+1, K);??>ll calculate(int P, int Q, int U, int V)<%	return no->query_seg(P+1, Q+1, U+1, V+1);??>int main()<%	init(2, 3);	update(0, 0, 20);	update(0, 2, 15);	update(1, 1, 12);	cout << calculate(0, 0, 0, 2) << "??/n";	cout << calculate(0, 0, 1, 1) << "??/n";	update(0, 1, 6);	update(1, 1, 14);	cout << calculate(0, 0, 0, 2) << "??/n";	cout << calculate(0, 0, 1, 1) << "??/n";	return 0;??>