H、小阳的贝壳

H、小阳的贝克

区间增加，区间求差的绝对值的最大值，区间gcd

1、，同理 ，所以维护一个差分数组，求区间和、最大值、最小值、gcd就可以A掉这题。

Code:

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
	int l;
	int r;
	ll sum;
	ll maxn;
	ll minn;
	ll gcds;
}que[MAXN * 4];
int ql, qr, n, m;
ll a[MAXN], in[MAXN], val;
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
	que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
	que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
	que[k].gcds = gcd(que[k << 1].gcds, que[k << 1 | 1].gcds);
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	if (left == right)
	{
		que[k].sum = a[left];
		que[k].maxn = a[left];
		que[k].minn = a[left];
		que[k].gcds = a[left];
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql == left && right == qr)
	{
		que[k].sum += val;
		que[k].maxn += val;
		que[k].minn += val;
		que[k].gcds = que[k].sum;
		return;
	}
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll querysum(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	imid;
	return querysum(lson) + querysum(rson);
}
ll querymax(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return -1000000000000000000;
	if (ql <= left && right <= qr)
		return que[k].maxn;
	imid;
	return max(querymax(lson), querymax(rson));
}
ll querymin(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 1000000000000000000;
	if (ql <= left && right <= qr)
		return que[k].minn;
	imid;
	return min(querymin(lson), querymin(rson));
}
ll querygcd(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].gcds;
	imid;
	return gcd(querygcd(lson), querygcd(rson));
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &in[i]);
		a[i] = in[i] - in[i - 1];
	}
	build();
	int q, w, op;
	while (m--)
	{
		scanf("%d%d%d", &op, &q, &w);
		if (op == 1)
		{
			scanf("%lld", &val);
			ql = q;
			qr = q;
			update();
			ql = w + 1;
			qr = w + 1;
			val = -val;
			update();
		}
		else if (op == 2)
		{
			ql = q + 1;
			qr = w;
			ll ans = max(0LL, max(querymax(), -querymin()));
			printf("%lld\n", ans);
		}
		else
		{
			ql = 1;
			qr = q;
			ll res1 = querysum();
			ql = q + 1;
			qr = w;
			ll res2 = querygcd();
			printf("%lld\n", abs(gcd(res1, res2)));
		}
	}
}