牛客-小阳的贝壳-区间gcd（线段树）

链接：https://ac.nowcoder.com/acm/contest/949/H
来源：牛客网

题目描述

小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为

输入描述:

第一行输入两个正整数

输出描述:

共 m 行，对于每个询问（操作 2 和操作 3）输出对应的结果。

示例1

输入

复制

输出

复制

分析：

　　这道题线段树，树状数组都用到啦

核心知识点gcd(a,b)==gcd(a,b-a), 这样的话我们维护一个差分数组，区间修改对于最大公约数的影响可以转化为对点的修改

a[]: 保存原始数据

b[]: 保存差分数据 b[i]=a[i]-a[i-1]

c[]: 当区间【l,r】增加时， c[l]+=x； c[r+1]-=x；即用树状数组维护a[]数组的区间更改； new_ai=ai+sum{c[x]} x范围从1到i

　　最后用线段树维护最大公约数就好啦

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,m,rt*2
 4 #define rson m+1,r,rt*2+1
 5 const int N=1e5+7;
 6 int a[N],b[N],c[N];
 7 int tg[4*N],tb[4*N];
 8 int n,m;
 9 inline int gcd (int x, int y) { return y ? gcd(y,x%y) : x; }
10 void pushup(int rt) {
11     tg[rt]=gcd(tg[rt*2], tg[rt*2+1]);
12     tb[rt]=max(abs(tb[rt*2]), abs(tb[rt*2+1]));
13 }
14 void build(int l, int r, int rt) {
15     if (l==r) {
16         tg[rt]=tb[rt]=b[l];
17         return ;
18     }
19     int m=(l+r)/2;
20     build(lson);
21     build(rson);
22     pushup(rt);
23     return ;
24 }
25 void update(int k, int val, int l, int r, int rt) {
26     if(l==r) {
27         tg[rt]+=val;
28         tb[rt]+=val;
29         return ;
30     }
31     int m=(l+r)/2;
32     if (k<=m) update(k,val,lson);
33     else      update(k,val,rson);
34     pushup(rt);
35     return ;
36 }
37 int q1 (int L, int R, int l, int r, int rt) {
38     if (r<L||l>R) return 0;
39     if (l>=L&&r<=R) return abs(tb[rt]);
40     int m=(l+r)/2;
41     return max(q1(L,R,lson),q1(L,R,rson));
42 }
43 int q2(int L, int R, int l, int r, int rt) {
44     if (r<L||l>R) return 0;
45     if (l>=L&&r<=R) return abs(tg[rt]);
46     int m=(l+r)/2;
47     int ans1=abs(q2(L,R,lson));
48     int ans2=abs(q2(L,R,rson));
49     return gcd(ans1,ans2);
50 }
51 void add(int k, int x) {
52     while (k<=n) {
53         c[k]+=x;
54         k+=k&(-k);
55     }
56 }
57 int get_sum(int k) {
58     int ans=0;
59     while(k) {
60         ans+=c[k];
61         k-=k&(-k);
62     }
63     return ans;
64 }
65 int main()
66 {
67     scanf("%d %d",&n,&m);
68     for (int i=1;i<=n;i++) {
69         scanf("%d",&a[i]);
70         b[i]=a[i]-a[i-1];
71     }
72     build(1,n,1);
73     while (m--) {
74         int op,l,r; scanf("%d %d %d",&op,&l,&r);
75         if (op==1) {
76             int x; scanf("%d",&x);
77             add(l,x); add(r+1,-x);
78             update(l,x,1,n,1);
79             if (r+1<=n) update(r+1,-x,1,n,1);
80         }
81         else if (op==2) {
82             if (l==r) printf("0
");
83             else      printf("%d
",q1(l+1,r,1,n,1));
84         }
85         else {
86             int now=a[l]+get_sum(l);
87             if (l==r) printf("%d
",now);
88             else      printf("%d
",gcd(now, q2(l+1,r,1,n,1)));
89         }
90     }
91     return 0;
92 }