关键点在于:
$$ gcd(a_1, a_2, …, a_k) = gcd(a_1, a_2 - a_1, a_3 - a_2, … , a_k - a_{k-1}) = gcd(a_1, gcd(a_2 - a_1, a_3 - a_2, … , a_k - a_{k-1}))\\ $$
所以我们可以用线段树来维护一个差分来找a_l,一个区间最大公约数来找gcd(a_l+1, a_l+2 , … , a_r)
也可以用树状数组维护差分数组来找a_1
树状数组维护前缀和
//树状数组维护前缀和
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
typedef long long LL;
int n, m;
LL a[N], tree[N];
LL lowbit(int x)
{
return x & -x;
}
LL sum(int x)
{
LL ans = 0;
for(int i = x; i ; i -= lowbit(i)) ans += tree[i];
return ans;
}
void add(int x, LL v)
{
for(int i = x; i <= n; i += lowbit(i)) tree[i] += v;
}
struct node
{
int l, r;
LL d;
}tr[N * 4];
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
void pushup(int u)
{
tr[u].d = gcd(tr[u << 1].d, tr[u << 1 | 1].d);
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, l, a[l] - a[l-1]};
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 t = tr[u].d + v;
tr[u] = {x, x, t};
return ;
}
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];
else
{
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;
res.d = gcd(left.d, right.d);
return res;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), add(i, a[i] - a[i - 1]);
build(1, 1, n);
char op[2];
LL l, r, d;
while(m--)
{
scanf("%s%lld%lld", op, &l, &r);
if(*op == 'C')
{
scanf("%lld", &d);
modify(1, l, d), add(l, d);
if(r + 1 <= n) modify(1, r + 1, -d), add(r + 1, -d);
}
else
{
LL res = sum(l);
node right = {0, 0, 0};
if(l + 1 <= r) right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(res, right.d)));
}
}
return 0;
}
线段树维护前缀和
//线段树维护前缀和
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
typedef long long LL;
int n, m;
LL a[N];
struct node
{
int l, r;
LL sum, d;
}tr[N * 4];
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.d = gcd(l.d, r.d);
}
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) tr[u] = {l, l, a[l] - a[l-1], a[l] - a[l-1]};
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 t = tr[u].sum + v;
tr[u] = {x, x, t, t};
}
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];
else
{
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()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
build(1, 1, n);
// for(int i = 1; i <= 10; i ++) cout << a[i] << endl;
char op[2];
LL l, r, d;
while(m--)
{
scanf("%s%lld%lld", op, &l, &r);
if(*op == 'C')
{
scanf("%lld", &d);
modify(1, l, d);
if(r + 1 <= n) modify(1, r + 1, -d);
}
else
{
auto left = query(1, 1, l);
node right = {0, 0, 0, 0};
if(l + 1 <= r) right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(left.sum, right.d)));
}
}
return 0;
}