[BZOJ5028]小Z的加油店

题目大意：

一个长度为\(n(n\le10^5)\)的数列，\(m(m\le10^5)\)次操作，支持区间加和区间\(\gcd\)。

思路：

线段树维护差分，\(\gcd(A_l,\cdots,A_r)\)就是区间\([l,r]\)差分的\(\gcd\)与\(A_r\)的\(\gcd\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1;

int a[N];

class SegmentTree {

	#define _left <<1

	#define _right <<1|1

	#define mid ((b+e)>>1)

	private:

		int gcd[N<<2],sum[N<<2];

		void push_up(const int &p) {

			gcd[p]=std::__gcd(gcd[p _left],gcd[p _right]);

			sum[p]=sum[p _left]+sum[p _right];

		}

	public:

		void build(const int &p,const int &b,const int &e) {

			if(b==e) {

				gcd[p]=sum[p]=a[b];

				return;

			}

			build(p _left,b,mid);

			build(p _right,mid+1,e);

			push_up(p);

		}

		void modify(const int &p,const int &b,const int &e,const int &x,const int &y) {

			if(b==e) {

				gcd[p]+=y;

				sum[p]+=y;

				return;

			}

			if(x<=mid) modify(p _left,b,mid,x,y);

			if(x>mid) modify(p _right,mid+1,e,x,y);

			push_up(p);

		}

		int query_gcd(const int &p,const int &b,const int &e,const int &l,const int &r) const {

			if(b==l&&e==r) return gcd[p];

			if(r<=mid) return query_gcd(p _left,b,mid,l,r);

			if(l>mid) return query_gcd(p _right,mid+1,e,l,r);

			return std::__gcd(query_gcd(p _left,b,mid,l,mid),query_gcd(p _right,mid+1,e,mid+1,r));

		}

		int query_sum(const int &p,const int &b,const int &e,const int &x) const {

			if(e==x) return sum[p];

			if(x<=mid) return query_sum(p _left,b,mid,x);

			if(x>mid) return sum[p _left]+query_sum(p _right,mid+1,e,x);

		}

	#undef _left

	#undef _right

	#undef mid

};

SegmentTree t;

int main() {

	const int n=getint(),m=getint();

	for(register int i=1;i<=n;i++) a[i]=getint();

	for(register int i=n;i>=1;i--) a[i]-=a[i-1];

	t.build(1,1,n);

	for(register int i=0;i<m;i++) {

		const int opt=getint(),l=getint(),r=getint();

		if(opt==1) {

			if(l<r) {

				printf("%d\n",std::abs(std::__gcd(t.query_sum(1,1,n,r),t.query_gcd(1,1,n,l+1,r))));

			} else {

				printf("%d\n",t.query_sum(1,1,n,r));

			}

		} else {

			const int v=getint();

			t.modify(1,1,n,l,v);

			if(r<n) t.modify(1,1,n,r+1,-v);

		}

	}

	return 0;

}