Interval GCD(单点修改，区间查询)
原题链接
题目描述
给定一个长度为 \(N\) 的数列 \(A\)，以及 \(M\) 条指令，每条指令可能是以下两种之一：
C l r d，表示把 \(A[l],A[l+1],…,A[r]\) 都加上 \(d\)。Q l r，表示询问 \(A[l],A[l+1],…,A[r]\) 的最大公约数(\(GCD\))。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 \(N,M\)。
第二行 \(N\) 个整数 \(A[i]\)。
接下来 \(M\) 行表示 \(M\) 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
- \(N≤500000,M≤100000\)
- \(1≤A[i]≤10^{18}\)
- \(|d|≤10^{18}\)
输入样例：
| 5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
|
输出样例：
前置知识
更相减损术
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。——出自《九章算术》
翻译：（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
证明
设 \(gcd(x,y)=d\)，则满足 \(x=k1*d\)，\(y=k2*d\)，易得 \(k1\) 与 \(k2\) 互质。
情况\(1\)：\(x=y\)。显然，\(gcd(x,y)=x=gcd(x,0)=gcd(x,y-x)\)。
情况\(2\)：用反证法。
假设 \(k1,(k2 - k1)\) 不互质，
令 \(gcb(k1.k2-k1) = m\) (\(m\)为正整数且\(m>1\));
即 \(k1,k2\) 有公约数 \(m\)，与 \(k1,k2\) 互质矛盾
所以假设不成立
即 \(k1,(k2 - k1)\) 互质
所以 \(gcb(x,y-x)=gcd(k1*d,k2*d-k1*d) = d = gcb(x,y)\)
综上，\(gcd(x,y)=gcd(x,y-x)\)。
命题得证
当然，此结论可用数学归纳法推广到一般，该性质对多个整数都成立。
即：\(gcd(x,y,z,...)=gcd(x,y-x,z-y,...)\)。
直观证明：
对于 \(gcd(x,y,z)=gcd(x,y-x,z-y):\)
\[gcd(x,y,z)=gcd(x,gcd(y,z))=gcd(x,gcd(y,z-y))=\]
\[gcd(x,y,z-y)=gcd(gcd(x,y),z-y)=\]
\[gcd(gcd(x,y-x),z-y)=gcd(x,y-x,z-y)\]
更多项依次类推。
算法与思路
首先，节点内信息需要包含我们所需要查询的答案，即区间内的最大公约数，记为 \(v\)。
根据更相减损术，如果我们有一个长度为 \(n\) 的数列 \(A\)，记为 \(A[1],A[2],...A[n]\)。对于区间 \([l, r]\)，有
\[v=gcd(A[l],A[l+1]-A[l],...A[r]-A[r-1])\]
可以发现，除了第一项，后面所有项都为 \(A[i+1]-A[i]\)，是明显的差分。同时第一项 \(A[l]\)，可以看作是区间 \([1,l]\) 所有差分数的和。
因此，节点内还需要一个信息，记为 \(sum\)，表示区间内差分数的总和。
左右子节点向父节点的转移函数为：
- \(u.sum = l.sum + r.sum;\)
- \(u.v = gcd(l.v, r.v);\)
线段树节点 \(node\)
注意，\(a[i]\) 和 \(d\) 最大值为 \(10^{18}\)，需要用 long long 来存储。
| typedef long long LL;
/*
* sum: 区间[l, r]的和
* v: 区间[l, r]中的最大公约数
*/
struct node {
int l, r;
LL sum, v;
} tr[N << 2];
|
pushup操作
1
2
3
4
5
6
7
8
9
10
11
12 | LL gcd(LL a, LL b) { // 欧几里得算法
return b ? gcd(b, a % b) : a;
}
void pushup(node &u, node &l, node &r) {
u.sum = l.sum + r.sum;
u.v = gcd(l.v, r.v);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
|
建树操作
叶子节点处的最大公约数为 \(w[r] - w[r-1]\)，\(sum\) 为差分，因此也为 \(w[r]-w[r-1]\)。
1
2
3
4
5
6
7
8
9
10
11
12 | void build(int u, int l, int r) {
if (l == r) { // 叶子节点
LL b = w[r] - w[r - 1];
tr[u] = {l, r, b, b};
} else {
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid); // 建左子树
build(u << 1 | 1, mid + 1, r); // 建右子树
pushup(u); // 修改父节点
}
}
|
修改操作
把位于 \(x\) 处的节点增加 \(v\)。
| void modify(int u, int x, LL v) {
if (tr[u].l == x && tr[u].r == x) { // 找到叶子节点
LL b = tr[u].sum + v;
tr[u] = {x, x, b, b};
} else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v); // 在左子树内
else modify(u << 1 | 1, x, v); // 在右子树内
pushup(u); // 修改父节点
}
}
|
查询操作
同样分为四种情况。
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 | node query(int u, int l, int r) {
// 1. 包含在区间内
// Tl-----Tr
// L-------------R
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
// 2. 在当前的左半区间
// Tl-----m-----Tr
// L---R
if (r <= mid) return query(u << 1, l, r);
// 3. 在当前的右半区间
// Tl-----m-----Tr
// L-----R
else if (l > mid) return query(u << 1 | 1, l, r);
// 4. 两边都有，都查询
// Tl----m----Tr
// L-----R
else {
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
node res;
pushup(res, left, right); // 合并答案
return res;
}
}
|
代码(无注释)
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 | #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
LL w[N];
struct node {
int l, r;
LL sum, v;
} tr[N << 2];
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
void pushup(node &u, node &l, node &r) {
u.sum = l.sum + r.sum;
u.v = gcd(l.v, r.v);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
if (l == r) {
LL b = w[r] - w[r - 1];
tr[u] = {l, r, b, b};
} else {
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, LL v) {
if (tr[u].l == x && tr[u].r == x) {
LL b = tr[u].sum + v;
tr[u] = {x, x, b, b};
} else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else {
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
node res;
pushup(res, left, right);
return res;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[i];
build(1, 1, n);
char op;
int l, r;
while (m--) {
cin >> op >> l >> r;
if (op == 'Q') {
auto left = query(1, 1, l);
node right({0, 0, 0, 0});
if (l + 1 <= r) right = query(1, l + 1, r);
cout << abs(gcd(left.sum, right.v)) << endl;
} else {
LL x; cin >> x;
modify(1, l, x);
if (r + 1 <= n) modify(1, r + 1, -x);
}
}
return 0;
}
|
运行结果
