246. 区间最大公约数 - AcWing题库 给定一个长度为 的数列 ，以及 条指令，每条指令可能是以下两种之一：
C l r d，表示把 都加上 。Q l r，表示询问 的最大公约数()。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行表示 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
,
,
输入样例：
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4输出样例：
1
2
4思路
区间修改+区间查询。
先不看修改, 先看咋查询。求两个数以上的最大公约数可以先计算出前两个, 然后把得到的结果与剩下的再求最大公约数。故我们只需要维护一个区间内的最大公约数即可。
最大公约数有这么一个性质： 证明 ⇐, 若d为左边的一个最大公约数, 那么它一定存在于右边且为最大值, 因为 左右都有 , 故 的差也是 d 的倍数, 同理后面都可以证明, 故 ⇐。 证明 >=, 因为d为右边的最大公约数, 即为 的约数, 而 包含 且 d 也是 的公约数, 故 d 也是 的公约数, 同理继续证明 , 可以得出 >=。
有了这个性质之后可以发现, 每一项刚好是减去前一项, 也就符合了差分数组, 即我们线段树维护的是差分, 既然是差分数组, 就可以在修改时把区间修改改为端点修改, 这题用不着lazy处理。
定义线段树节点值 sum 为区间和, gcd 为区间最大公约数。更新同样pushup分离, 多态定义方便重用。修改 区间就 update(L, x), update(R+1,-x)。
返回查询同样返回 Node 节点, 区间的最大公约数就是 。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#define lson l, mid, u << 1
#define rson mid + 1, r , u << 1 | 1
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
struct Node {
ll sum, gcd;
}t[N * 4];
int n,m;
ll a[N];
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.gcd = gcd(l.gcd, r.gcd);
}
void pushup(int u)
{
pushup(t[u], t[u << 1], t[u << 1 | 1]);
}
void build(int l, int r, int u = 1)
{
if(l == r)
{
ll b = a[r] - a[r - 1];
t[u] = {b , b};
return;
}
int mid = l + r >> 1;
build(lson), build(rson);
pushup(u);
}
void update(int pos, ll v, int l = 1, int r = n, int u = 1)
{
if(pos == l && pos == r)
{
ll b = t[u].sum + v;
t[u] = {b,b};
return;
}
int mid = l + r >> 1;
if(pos <= mid) update(pos, v, lson);
else update(pos, v, rson);
pushup(u);
}
Node query(int L, int R, int l = 1, int r = n, int u = 1)
{
if(L <= l && r <= R)
return t[u];
int mid = l + r >> 1;
if(L > mid) return query(L, R, rson);
else if(R <= mid) return query(L,R,lson);
else {
auto left = query(L,R,lson);
auto right = query(L,R,rson);
Node res;
pushup(res, left, right);
return res;
}
pushup(u);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
build(1,n);
char op[2];
int l,r;
ll x;
while(m--)
{
cin >> op >> l >> r;
if(op[0] == 'Q')
{
auto left = query(1, l);
auto right = query(1 + l, r);
cout << abs(gcd(left.sum, right.gcd)) << endl;
}
else {
cin >> x;
update( l, x);
if(r + 1 <= n)
update( r + 1, -x);
}
}
return 0;
}