4302 Interval GCD 区间加以及求区间gcd

127 阅读 0 评论 84 点赞

我是靠谱客的博主现实海燕，这篇文章主要介绍4302 Interval GCD 区间加以及求区间gcd，现在分享给大家，希望可以做个参考。

题目链接：http://contest-hunter.org:83/contest/0x40%E3%80%8C%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%BF%9B%E9%98%B6%E3%80%8D%E4%BE%8B%E9%A2%98/4302%20Interval%20GCD

题意：

两种线段树操作，1是区间加，2是求区间gcd；

做法：

如果是单点更新其实就是正常求gcd就好了，但是这是区间更新，还是没一个数都要加，就会比较麻烦，这里有一个公式 $gcd(a,b,c,....z)=gcd(a,b-a,c-b,...,z-y)$ ,即从第二项开始每一项减去前一项的gcd，这样的话就会发现区间加就只需要改变两个值就好了，会让操作变得非常方便，但是由于a还是原来的a，所以还要是要更新一个基数情况，即在原来情况上改变后这个数变成了多少，那么这个用树状数组稍微维护一下就好了。

复制代码

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=500005;
int n,m;
ll a[maxn],b[maxn];
ll val[maxn<<2],sum[maxn*2];
void push_up(int rt){
    val[rt]=__gcd(val[lson],val[rson]);
}
void build(int l,int r,int rt){
    if(l==r){
        val[rt]=b[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,lson);
    build(mid+1,r,rson);
    push_up(rt);
}
ll query(int ql,int qr,int l,int r,int rt){
    if(ql<=l&&r<=qr){
        return abs(val[rt]);
    }
    int mid=(l+r)/2;
    ll ret=0;
    if(ql<=mid) ret=__gcd(ret,query(ql,qr,l,mid,lson));
    if(qr>mid) ret=__gcd(ret,query(ql,qr,mid+1,r,rson));
    return abs(ret);
}
void update(int pos,int l,int r,int rt,ll v){
    if(l==r){
        val[rt]+=v;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,l,mid,lson,v);
    if(pos>mid) update(pos,mid+1,r,rson,v);
    push_up(rt);
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,ll v){
    while(x<maxn){
        sum[x]+=v;
        x+=lowbit(x);
    }
}
ll Query(int x){
    ll ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){

cin>>n>>m;
    rep(i,1,n){
        scanf("%lld",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    build(1,n,1);
    rep(z,1,m){
        char op[5];
        int L,R;
        scanf("%s%d%d",op,&L,&R);
        if(op[0]=='Q'){
            ll fi=a[L]+Query(L);
            ll se = query(L+1,R,1,n,1);
            printf("%lldn",__gcd(fi,se));
        }
        else{
            ll aim;
            scanf("%lld",&aim);
            update(L,1,n,1,aim);
            if(R<n) update(R+1,1,n,1,-aim);
            add(L,aim);
            add(R+1,-aim);
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=500005;
int n,m;
ll a[maxn],b[maxn];
ll val[maxn<<2],sum[maxn*2];
void push_up(int rt){
    val[rt]=__gcd(val[lson],val[rson]);
}
void build(int l,int r,int rt){
    if(l==r){
        val[rt]=b[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,lson);
    build(mid+1,r,rson);
    push_up(rt);
}
ll query(int ql,int qr,int l,int r,int rt){
    if(ql<=l&&r<=qr){
        return abs(val[rt]);
    }
    int mid=(l+r)/2;
    ll ret=0;
    if(ql<=mid) ret=__gcd(ret,query(ql,qr,l,mid,lson));
    if(qr>mid) ret=__gcd(ret,query(ql,qr,mid+1,r,rson));
    return abs(ret);
}
void update(int pos,int l,int r,int rt,ll v){
    if(l==r){
        val[rt]+=v;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,l,mid,lson,v);
    if(pos>mid) update(pos,mid+1,r,rson,v);
    push_up(rt);
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,ll v){
    while(x<maxn){
        sum[x]+=v;
        x+=lowbit(x);
    }
}
ll Query(int x){
    ll ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){

    cin>>n>>m;
    rep(i,1,n){
        scanf("%lld",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    build(1,n,1);
    rep(z,1,m){
        char op[5];
        int L,R;
        scanf("%s%d%d",op,&L,&R);
        if(op[0]=='Q'){
            ll fi=a[L]+Query(L);
            ll se = query(L+1,R,1,n,1);
            printf("%lldn",__gcd(fi,se));
        }
        else{
            ll aim;
            scanf("%lld",&aim);
            update(L,1,n,1,aim);
            if(R<n) update(R+1,1,n,1,-aim);
            add(L,aim);
            add(R+1,-aim);
        }
    }
    return 0;
}