最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天快报!AcWing246. 区间最大公约数

来源：博客园

题目描述

给定一个长度为 \(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\))。

对于每个询问，输出一个整数表示答案。

解题思路

\(\qquad\)区间问题可以用线段树，但是这个既要区间求\(GCD\)又要区间加，怎么办。

\(\qquad\qquad\qquad\qquad\) 这时候老祖宗的智慧就来了

更向减损术的扩展版本

\(\qquad\large gcd(x_0,x_1,x_2,x_3....x_n) = gcd(x_0,x_1-x_0,x_2-x_1.....x_n-x_{n-1})\)看出了什么，\(\LARGE 差分啊 啊啊啊啊\)

\(\qquad\)刚好差分可以很好地维护前缀和，支持区间修改，所以我们就可以用一颗差分树状数组（区间修改，单点查询）来支持我们的\(1\)操作，然后用一颗支持单点修改，区间查询的线段树来维护区间的\(GCD\)，这样就可以实现我们的区间\(GCD\)查询了。

很重要的注意事项：

\(\qquad\)我们查询的时候需要查询区间\([l,r]\)的区间\(GCD\)，应该用\(a[l]\)和\([l+1,r]\)的区间\(GCD\)再取一个\(GCD\)，为什么？

\(\qquad\)原因如下：

\(\qquad\)\(\qquad\)毕竟我们的\(GCD\)查询是用差分实现的，那么对于每一段区间\([l,r]\)的\(GCD\)，可以用更向减损术这样表示：

\(\quad\large gcd(a_l, a_{l+1}, a_{l+2}...a_{r-1}, a_{r}) = gcd(a_{l},a_{l+1}-a_{l},....a_{r}-a_{r-1})\)

观察上式可以发现，我们后半段的值都是差分值，是可以直接用线段树查询的，但是我们的第一个值都是\(a_l\)，它在线段树中的值是一个差分值\(a_l-a_{l-1}\)，所以这回导致我们的查询操作出问题，所以应该揪出来特殊处理。

然后这题我们可以用树状数组动态维护每个数的值，代码如下

void add(int x, LL v) {    for (; x <= n; x += x & -x) c[x] += v;}LL ask(int x) {    LL res = 0;    for (; x; x -= x & -x) res += c[x];    return res; }

在main()函数中：

scanf("%d", &a[i]), add(i, a[i] - a[i - 1]);

代码

#include #include using namespace std;using LL = long long;const int N = 5e5 + 10;LL a[N], c[N], b[N]; int n, m;struct Seg {    int l, r;    LL v;    #define l(x) tr[x].l    #define r(x) tr[x].r    #define v(x) tr[x].v} tr[N << 2];    void add(int x, LL v) {    for (; x <= n; x += x & -x) c[x] += v;}LL ask(int x) {    LL res = 0;    for (; x; x -= x & -x) res += c[x];    return res; }LL gcd(LL a, LL b) {    return abs(__gcd(a, b));}void build(int p, int l, int r) {    l(p) = l, r(p) = r;    if (l == r) return void (v(p) = b[l]);    int mid = l + r >> 1;    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);    v(p) = gcd(v(p << 1), v(p << 1 | 1));}void modify(int p, int x, LL v) {    if (l(p) == x && r(p) == x) return void (v(p) += v);        int mid = l(p) + r(p) >> 1;    if (x <= mid) modify(p << 1, x, v);    else modify(p << 1 | 1, x, v);        v(p) = gcd(v(p << 1), v(p << 1 | 1));}LL query(int p, int l, int r) {    if (l(p) >= l && r(p) <= r) return v(p);        int mid = l(p) + r(p) >> 1;    LL v = 0;    if (l <= mid) v = gcd(v, query(p << 1, l, r));    if (r > mid) v = gcd(v, query(p << 1 | 1, l, r));        return v;}int main() {    scanf("%d%d", &n, &m);        for (int i = 1; i <= n; i ++ )         scanf("%lld", &a[i]), b[i] = a[i] - a[i - 1], add(i, b[i]);        build(1, 1, n);        while (m -- )     {        char op[2]; int l, r;        scanf("%s%d%d", op, &l, &r);                if (op[0] == "C")         {            LL d; scanf("%lld", &d);            modify(1, l, d);            if (r < n) modify(1, r + 1, -d);            add(l, d), add(r + 1, -d);        }        else {            LL res = l < r ? query(1, l, r) : 0;            printf("%lld\n", res);        }    }        return 0;}

关键词： 注意事项 整数表示 区间查询