2014-06-09 - HIR180's diary

■ IOI 2013 GAME 23:34

80点はJOIのapplesという問題をといたことがあるとかけます。

100点はなんかすると取れます。(ノード内のデータ構造を平衡二分探索木っぽく書くととれるらしい)

(ソース: https://gist.github.com/msg555/6025939)

#include 
#include 
#include 
#include 
using namespace std;

#define SIZE (1<<30)
typedef long long ll;
int r,c,n;

struct node2
{
	node2 *lch,*rch;
	ll value;
	node2()
	{
		lch = (node2 *)NULL;
		rch = (node2 *)NULL;
		value = 0LL;
	}
};
struct node1
{
	node1 *lch,*rch;
	node2 *act;
	node1()
	{
		lch = (node1 *)NULL;
		rch = (node1 *)NULL;
		act = (node2 *)NULL;
	}
};
node1 *root;
void update2(node2 *cur,int l,int r,int a,ll val)
{
	if(l == a && a == r)
	{
		cur->value = val;
		return;
	}
	if(l <= a && a <= (l+r)/2)
	{
		if(cur->lch == (node2 *)NULL)
		{
			cur->lch = new node2;
		}
		update2(cur->lch,l,(l+r)/2,a,val);
	}
	else
	{
		if(cur->rch == (node2 *)NULL)
		{
			cur->rch = new node2;
		}
		update2(cur->rch,(l+r)/2+1,r,a,val);
	}
	ll lb = (cur->lch == (node2 *)NULL?0:cur->lch->value);
	ll ub = (cur->rch == (node2 *)NULL?0:cur->rch->value);
	cur->value = __gcd(lb,ub);
}
ll query2(node2 *cur,int l,int r,int a,int b)
{
	if(rreturn 0LL;
	if(a<=l && r<=b) return cur->value;
	ll lb = (cur->lch == (node2 *)NULL?0:query2(cur->lch,l,(l+r)/2,a,b));
	ll ub = (cur->rch == (node2 *)NULL?0:query2(cur->rch,(l+r)/2+1,r,a,b));
	return __gcd(lb,ub);
}
void update1(node1 *cur,int l,int r,int a,int b,ll val)
{
	if(cur->act == (node2 *)NULL)
	{
		cur->act = new node2;
	}
	if(l==r)
	{
		update2(cur->act,0,SIZE-1,b,val);
		return ;
	}
	if(l <= a && a <= (l+r)/2)
	{
		if(cur->lch == (node1 *)NULL)
		{
			cur->lch = new node1;
		}
		update1(cur->lch,l,(l+r)/2,a,b,val);
	}
	else
	{
		if(cur->rch == (node1 *)NULL)
		{
			cur->rch = new node1;
		}
		update1(cur->rch,(l+r)/2+1,r,a,b,val);
	}
	ll lb=0,ub=0;
	if(cur->lch != (node1 *)NULL && cur->lch->act !=(node2 *)NULL) lb = query2(cur->lch->act,0,SIZE-1,b,b);
	if(cur->rch != (node1 *)NULL && cur->rch->act !=(node2 *)NULL) ub = query2(cur->rch->act,0,SIZE-1,b,b);
	update2(cur->act,0,SIZE-1,b,__gcd(lb,ub));
}
ll query(node1 *cur,int l,int r,int ax,int bx,int ay,int by)
{
	if(rreturn 0LL;
	if(ax<=l && r<=bx)
	{
		return (cur->act == (node2 *)NULL?0:query2(cur->act,0,SIZE-1,ay,by));
	}
	ll lb = (cur->lch == (node1 *)NULL?0:query(cur->lch,l,(l+r)/2,ax,bx,ay,by));
	ll ub = (cur->rch == (node1 *)NULL?0:query(cur->rch,(l+r)/2+1,r,ax,bx,ay,by));
	return __gcd(lb,ub);
}
int main()
{
	root = new node1;
	scanf("%d%d%d",&r,&c,&n);
	for(int i=0;iint t; scanf("%d",&t);
		if(t == 1)
		{
			int x,y; ll v;
			scanf("%d%d%lld",&x,&y,&v);
			update1(root,0,SIZE-1,x,y,v);
		}
		else
		{
			int ax,ay,bx,by;
			scanf("%d%d%d%d",&ax,&ay,&bx,&by);
			printf("%lld\n",query(root,0,SIZE-1,ax,bx,ay,by));
		}
	}
}