[线段树+数论]ContestHunter4302 IntervalGCD

描述

给定一个长度为N的数列A,以及M条指令 (N≤5*10^5, M<=10^5),每条指令可能是以下两种之一:
“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。
“Q l r”,表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

输入格式

第一行两个整数N,M,第二行N个整数Ai,接下来M行每条指令的格式如题目描述所示。

输出格式

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

样例输入

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

数据范围与约定

N,M≤2*10^5,l<=r,数据保证任何时刻序列中的数都是不超过2^62-1的正整数。

解题思路

本题综合考察线段树与数论,是一道非常棒的题目。
在解决这道题之前我们先来回顾一下线段树可以做些什么。
线段树可以维护连续的区间。。。

代码实现

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn=2000200;
ll n,m,a[maxn],d[maxn];
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll num[maxn<<2];
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
inline void pushup(ll rt) {num[rt]=gcd(num[rt<<1],num[rt<<1|1]);}
inline void build(ll rt,ll l,ll r) {
    if(l==r) {num[rt]=d[l];return;}
    build(lson);build(rson);pushup(rt);
}
inline void update(ll pos,ll d,ll rt,ll l,ll r) {
    if(l==r) {num[rt]+=d;return;}
    if(pos<=mid) update(pos,d,lson);
    else update(pos,d,rson);
    pushup(rt);
}
inline ll query(ll L,ll R,ll rt,ll l,ll r) {
    if(l>r) return 1;
    if(L<=l && r<=R) return num[rt];
    if(R<=mid) return query(L,R,lson);
    else if(L>mid) return query(L,R,rson);
    else return gcd(query(L,R,lson),query(L,R,rson));
}
struct Tree {
    ll c[maxn];
    ll lowbit(ll x) {
        return x&-x;
    }
    void add(ll x,ll p) {
        while(x<=n) {
            c[x]+=p;
            x+=lowbit(x);
        }
    }
    ll sum(ll x) {
        ll ret=0;
        while(x) {
            ret+=c[x];
            x-=lowbit(x);
        }
        return ret;
    }
}t;
int main() {
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<n;i++) d[i]=a[i+1]-a[i];
    t.add(1,a[1]);
    for(ll i=2;i<=n;i++) t.add(i,d[i-1]);
    build(1,1,n);
    char opt[2];
    for(ll i=1;i<=m;i++) {
        ll l,r,d;
        scanf("%s",opt);scanf("%lld%lld",&l,&r);
        if(opt[0]=='Q') printf("%lld\n",abs(gcd(t.sum(l),query(l,r-1,1,1,n))));
        if(opt[0]=='C') {
            scanf("%lld",&d);
            t.add(l,d);
            if(l>1) update(l-1,d,1,1,n);
            if(r<n) t.add(r+1,-d),update(r,-d,1,1,n);
        }
    }
    return 0;
}
点赞

发表评论