链接：https://ac.nowcoder.com/acm/contest/1033/B
来源：牛客网
题目描述
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
输入描述:
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出描述:
对于每个询问，输出一个整数表示答案。
每个答案占一行。
示例1
输入
复制
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
注意到多个数gcd的性质：gcd(x, y, z) = gcd(x, y - x, z - y)，和区间加减法结合起来就可做了。具体参见蓝书p217.
注意：可能要进行很多次区间加法，因此要开long long。
区间修改的时候if(r < n) 才进行change(1, r + 1 , -d); 否则是没有意义的（因为永远用不到r + 1，但是r + 1却会影响线段树上一层结点的值）
ask的时候要对答案加绝对值（因为对某一个点可能进行多次减法变成负数了）。
#include <iostream>
#define int long long
using namespace std;
int n, m, a[500005], b[500005], c[500005];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
struct SegmentTree
{
int l, r, dat;
} t[2000005];
void build(int p, int l, int r)
{
t[p].l = l, t[p].r = r;
if(l == r)
{
t[p].dat = b[l];
return;
}
int mid = (l + r) >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].dat = gcd(t[2 * p].dat, t[2 * p + 1].dat);
}
void change(int p, int x, int v)//需要对差分数组进行单点修改
{
if(t[p].l == t[p].r)
{
t[p].dat += v;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) change(2 * p, x, v);
else change(2 * p + 1, x, v);
t[p].dat = gcd(t[2 * p].dat, t[2 * p + 1].dat);
}
int ask(int p, int l, int r)
{
if(t[p].l >= l && t[p].r <= r)
{
return abs(t[p].dat);//注意要绝对值
}
int mid = (t[p].l + t[p].r) >> 1;
int ans = 0x3f3f3f3f;
if(l <= mid) ans = ask(2 * p, l, r);
if(r > mid)
{
if(ans != 0x3f3f3f3f) ans = gcd(ans, ask(2 * p + 1, l, r));
else ans = ask(2 * p + 1, l, r);
}
return abs(ans);
}
//以下为BIT
int query(int x)//查询的是前缀和
{
int ans = 0;
for(; x; x -= x & -x) ans += c[x];
return ans;
}
void add(int x, int y)
{
for(; x <= 500005; x += x & -x)
{
c[x] += y;
}
}
signed main()
{
//freopen("data.txt", "r", stdin);
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i] - a[i - 1];
}
for(int i = 1; i <= n; i++)
{
add(i, b[i]);//树状数组维护的是差分序列 因此这里应该初始化为b[i]?
}
build(1, 1, n);
//cout << ask(1, 2, n) << endl;
for(int i = 1; i <= m; i++)
{
char op;
int l, r, d;
cin >> op;
if(op == 'Q')
{
cin >> l >> r;
//cout << query(l) << ' ' << ask(1, l + 1, r) << endl;
if(l < r) cout << gcd(query(l), ask(1, l + 1, r)) << endl;
else cout << gcd(query(l), 0) << endl;
}
else
{
cin >> l >> r >> d;
change(1, l, d);
if(r < n) change(1, r + 1 , -d);//要判r < n
add(l, d);
add(r + 1, -d);
}
}
return 0;
}