传送门 ↬\looparrowright

题目描述

小阳手中一共有 nn 个贝壳，每个贝壳都有颜色，且初始第 ii 个贝壳的颜色为 colicol_i。 现在小阳有 33 种操作。
1 l r x\text{1 l r x}：给 [l，r][l，r] 区间里所有贝壳的颜色值加上 xx。
2 l r\text{2 l r}：询问[l，r][l，r] 区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 l=rl=r 输出 00）。
3 l r\text{3 l r}：询问 [l，r][l，r] 区间里所有贝壳颜色值的最大公约数。

输入描述

第一行输入两个正整数 n,mn,m，分别表示贝壳个数和操作个数。
第二行输入 nn 个数 colicol_i，表示每个贝壳的初始颜色。
第三到第 m+2m + 2 行，每行第一个数为 optopt，表示操作编号。接下来的输入的变量与操作编号对应。

输出描述

共 mm 行，对于每个询问（操作 22 和操作 33）输出对应的结果。

示例1

输入
5 6
2 2 3 3 3
1 2 3 3
2 2 4
3 3 5
1 1 4 2
3 2 3
2 3 5
输出
3
3
1
3

备注

1≤n,m≤105,1≤coli,x≤103,1≤opt≤3,1≤l≤r≤n1 \leq n,m \leq 10^5,1 \leq col_i,x \leq 10^3,1 \leq opt \leq 3,1 \leq l \leq r \leq n。

分析

区间修改查询的操作，第一反应是区间修改和区间查询的线段树，但是一时无从下手。
对于数组的区间修改，另一个常用的策略是使用差分数组，设数组 colicol_i 的差分数组为 did_i。
进行操作 11 区间加时，相当于对差分数组 dld_l 和 dr+1d_{r+1} 的单点修改。因此不妨用一颗线段树维护 did_i，对其进行单点修改。
进行操作 22 时，求的是区间 [l,r][l,r] 内 ∣coli−coli−1∣(l+1≤i≤r)|col_i-col_{i-1}|(l+1\le i\le r) 的最大值，也就是求区间[l+1,r][l+1,r] 内 ∣di∣|d_i| 的最大值。因此不妨用一颗线段树维护区间内 ∣di∣|d_i| 的最大值。
进行操作 33 时，显然有 gcd⁡(coll,coll+1,⋯ ,colr)\gcd(col_l,col_{l+1},\cdots,col_r)==gcd⁡(coll,∣coll+1−coll∣,⋯ ,∣colr−colr−1∣)\gcd(col_l,|col_{l+1}-col_l|,\cdots,|col_r-col_{r-1}|)==gcd⁡(coli,∣dl+1∣,⋯ ,∣dr∣)\gcd(col_i,|d_{l+1}|,\cdots,|d_r|)==gcd⁡(∑i=1ldi,∣dl+1∣,⋯ ,∣dr∣)\gcd(\sum\limits_{i=1}^l d_i,|d_{l+1}|,\cdots,|d_r|) 。因此不妨用一颗线段树维护区间内 ∣di∣|d_i| 的最小公倍数和 did_i 的区间和。
综上所述，线段树上节点包含的信息有，区间内 did_i 的和、区间内∣di∣|d_i| 的最大公约数、区间内 ∣di∣|d_i| 的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100006
using namespace std;
int col[N];
int d[N];//差分
int n,m;
struct SegmentTree
{
	int l,r;
	int maximum;//区间内|d[i]|最大值
	int gcd;//区间内|d[i]|最大公约数
	int sum;//区间内d[i]的和
}tree[N<<2];
void pushup(int id)//自底向上递推
{
	int ls=id<<1;
	int rs=id<<1|1;
	tree[id].gcd=__gcd(tree[ls].gcd,tree[rs].gcd);
	tree[id].maximum=max(tree[ls].maximum,tree[rs].maximum);
	tree[id].sum=tree[ls].sum+tree[rs].sum;
}
void build(int id,int l,int r)//建树
{
	tree[id].l=l;
	tree[id].r=r;
	if(l==r)
	{
		tree[id].gcd=tree[id].maximum=abs(d[l]);
		tree[id].sum=d[l];
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	pushup(id);
}
int query_gcd(int id,int l,int r)//查询区间gcd
{
	if(l<=tree[id].l&&tree[id].r<=r) return tree[id].gcd;
	int mid=tree[id].l+tree[id].r>>1;
	int res=0;
	if(l<=mid) res=__gcd(res,query_gcd(id<<1,l,r));
	if(r>=mid+1) res=__gcd(res,query_gcd(id<<1|1,l,r));
	return res;
}
int query_sum(int id,int l,int r)//查询区间和
{
	if(l<=tree[id].l&&tree[id].r<=r) return tree[id].sum;
	int mid=tree[id].l+tree[id].r>>1;
	int res=0;
	if(l<=mid) res+=query_sum(id<<1,l,r);
	if(r>=mid+1) res+=query_sum(id<<1|1,l,r);
	return res;
}
int query_max(int id,int l,int r)//查询区间最大值
{
	if(l<=tree[id].l&&tree[id].r<=r) return tree[id].maximum;
	int mid=tree[id].l+tree[id].r>>1;
	int res=0;
	if(l<=mid) res=max(res,query_max(id<<1,l,r));
	if(r>=mid+1) res=max(res,query_max(id<<1|1,l,r));
	return res;
}
void update(int id,int pos,int x)//单点更新
{
	if(tree[id].l==pos&&tree[id].r==pos)
	{
		tree[id].sum+=x;
		tree[id].maximum=abs(tree[id].sum);
		tree[id].gcd=abs(tree[id].sum);
		return;
	}
	int mid=tree[id].l+tree[id].r>>1;
	if(pos<=mid) update(id<<1,pos,x);
	else update(id<<1|1,pos,x);
	pushup(id);
}
int main()
{
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++) scanf("%d",col+i);
	for(i=1;i<=n;i++) d[i]=col[i]-col[i-1];
	build(1,1,n);
	while(m--)
	{
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==2) l==r?puts("0"):printf("%d\n",query_max(1,l+1,r));
		else if(opt==3) printf("%d\n",__gcd(query_sum(1,1,l),query_gcd(1,l+1,r)));
		else
		{
			int x;
			scanf("%lld",&x);
			//对差分数组进行单点更新
			update(1,l,x);
			if(r<n) update(1,r+1,-x);
		}
	}
	return 0;
}