区间加值，区间gcd, 牛客949H

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

#牛客小白月赛16H　小阳的贝壳

题目链接

题意

维护一个数组，支持以下操作:

1: 区间加值

2: 询问区间相邻数差的绝对值的最大值

3: 询问区间gcd ## 题解

设原数组为\(a\), 用线段树维护\(b[i] = a[i] - a[i - 1]\),

线段树维护三个值：min, max, gcd

对于操作1:

L 位置加上x, R + 1位置减去x

对于操作2:

查询区间(L + 1, R) 的 min, max, 取绝对值大者

对于操作3:

考虑gcd的性质

\(gcd(a, b, c, d, ...) = gcd(a, b - a, c - b, d - c, ...)\)

查询区间(L + 1, R) 的 gcd, 就是\(gcd(b - a, c - b, d - c, ...)\)

然后用另一个东西维护原来的a数列

可以用另一颗线段树lazy标记维护

我用的是树状数组差分，将区间更新和单点查询转化为单点更新和前缀和查询

代码

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
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int mx[N << 2], mn[N << 2], g[N << 2], c[N], a[N], b[N];
int n, m, op, l, r, x;

void add(int pos, int val) {
	for(; pos <= n; pos += pos & -pos)
		c[pos] += val;
}

int ask(int pos) {
	int ans = 0;
	for(; pos; pos -= pos & -pos)
		ans += c[pos];
	return ans;
}

void pushup(int rt) {
	mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
	mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
	g[rt] = __gcd(g[rt << 1], g[rt << 1 | 1]);
}

void build(int rt, int l, int r) {
	if(l == r) {
		mx[rt] = mn[rt] = g[rt] = b[l];
		return;
	}
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}

void update(int rt, int l, int r, int pos, int val) {
	if(l == r) {
		mx[rt] += val;
		mn[rt] += val;
		g[rt] += val;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid)
		update(rt << 1, l, mid, pos, val);
	else
		update(rt << 1 | 1, mid + 1, r, pos, val);
	pushup(rt);
}

int querymax(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R) {
		return max(abs(mn[rt]), abs(mx[rt]));
	}
	int mid = l + r >> 1, ans = 0;
	if(L <= mid)
		ans = max(ans, querymax(rt << 1, l, mid, L, R));
	if(R > mid)
		ans = max(ans, querymax(rt << 1 | 1, mid + 1, r, L, R));
	return ans;
}

int querygcd(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R) {
		return g[rt];
	}
	int mid = l + r >> 1, ans = 0;
	if(L <= mid)
		ans = __gcd(ans, querygcd(rt << 1, l, mid, L, R));
	if(R > mid)
		ans = __gcd(ans, querygcd(rt << 1 | 1, mid + 1, r, L, R));
	return abs(ans);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		add(i, a[i] - a[i - 1]);
		b[i] = a[i] - a[i - 1];
	}
	build(1, 1, n);
	while(m--) {
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1) {
			scanf("%d", &x);
			add(l, x);
			update(1, 1, n, l, x);
			if(r != n) {
				add(r + 1, -x);
				update(1, 1, n, r + 1, -x);
			}
		}
		else if(op == 2) {
			if(l == r)
				puts("0");
			else
				printf("%d\n", querymax(1, 1, n, l + 1, r));
		}
		else {
			int a = ask(l), b;
			if(l == r)
				b = 0;
			else
				b = querygcd(1, 1, n, l + 1, r);
			printf("%d\n", __gcd(a, b));
		}
	}
	return 0;
}