ARC #017 D ARCたんクッキー

https://twitter.com/okuraofvegetabl/status/437286426967699457
人間は、クソ。
じゃなくて、
俺が、クソ。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int SIZE=1<<19;
struct node
{
	ll gcd,left,right,lazy;
	node(ll gcd=0ll,ll left=0ll,ll right=0ll,ll lazy=0ll):gcd(gcd),left(left),right(right),lazy(lazy){}
};
struct segtree
{
	node seg[SIZE*2];
	segtree()
	{
		for(int i=0;i<SIZE*2;i++)seg[i]=node();
	}
	void init(int k,ll x)
	{
		k+=SIZE-1;
		seg[k].left=x;
		seg[k].right=x;
	}
	void build()
	{
		for(int k=SIZE-2;k>=0;k--)seg[k]=update(seg[k*2+1],seg[k*2+2]);
	}
	inline void lazy_evaluate(int k)
	{
		seg[k].left+=seg[k].lazy;
		seg[k].right+=seg[k].lazy;
		if(k<SIZE-1)
		{
			seg[k*2+1].lazy+=seg[k].lazy;
			seg[k*2+2].lazy+=seg[k].lazy;
		}
		seg[k].lazy=0ll;
	}
	inline node update(node a,node b)
	{
		node par;
		par.left=a.left;
		par.right=b.right;
		par.gcd=__gcd(__gcd(a.gcd,b.gcd),abs(b.left-a.right));
		return par;
	}
	void add(int a,int b,ll x,int k,int l,int r)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return;
		else if(a<=l&&r<=b)
		{
			seg[k].lazy+=x;
			lazy_evaluate(k);
			return;
		}
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
		seg[k]=update(seg[k*2+1],seg[k*2+2]);
		return;
	}
	node query(int a,int b,int k,int l,int r)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return node();
		else if(a<=l&&r<=b)return seg[k];
		node left=query(a,b,k*2+1,l,(l+r)/2);
		node right=query(a,b,k*2+2,(l+r)/2,r);
		seg[k]=update(seg[k*2+1],seg[k*2+2]);
		return update(left,right);
	}
	ll ans(int a,int b)
	{
		node ans=query(a,b,0,0,SIZE);
		return __gcd(ans.gcd,abs(ans.left));
	}
};
segtree seg;
int main()
{
	int n,m;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		ll k;
		scanf("%lld",&k);
		seg.init(i,k);
	}
	seg.build();
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		int t,l,r;
		scanf("%d %d %d",&t,&l,&r);
		l--;
		if(t==0)
		{
			printf("%lld\n",seg.ans(l,r));
		}
		else
		{
			seg.add(l,r,t,0,0,SIZE);
		} 
	}
	return 0;
}