[Algorithm] cpp 백준 12858번: Range GCD

문제

링크: https://www.acmicpc.net/problem/12858
요약: 길이 \(N\)의 수열에 대해 두 연산을 처리합니다. (1) T>0이면 구간 [A,B]에 T를 더하고, (2) T=0이면 구간 [A,B]의 최대공약수(GCD)를 출력합니다.

입력/출력

1
2
3
4
5
6
7
8
<입력>
N
A1 A2 ... AN
Q
T A B   (Q줄)  // T>0: 구간 덧셈, T=0: 구간 GCD 질의

<출력>
각 T=0 질의에 대한 답을 한 줄에 하나씩 출력

접근 개요

핵심 등식: \(\gcd(A[l..r]) = \gcd(|A[l]|,\ \gcd(D[l+1..r]))\) where \(D[i] = A[i] - A[i-1]\).
구간 덧셈 [l,r]+=T는 차분 배열에서 D[l]+=T, D[r+1]-=T 두 점 갱신만 수행합니다.
따라서 D의 구간 GCD를 유지하는 세그먼트 트리와, 현재 A[l]을 복원하는 점 조회용 펜윅트리(BIT)를 함께 사용하면 각 연산을 \(O(\log N)\)에 처리할 수 있습니다.

flowchart LR
  Q{연산} -->|T>0, [l,r]+=T| U[BIT.rangeAdd(l,r,T)]
  U --> D1[D[l]+=T, D[r+1]-=T]
  D1 --> S1[SegTree.pointSet(l), pointSet(r+1)]
  Q -->|T=0, GCD[l,r]?| L1[a[l]=A[l]+BIT.sum(l)]
  L1 --> G1[G = SegTree.gcd(l+1,r)]
  G1 --> A1[답 = gcd(|a[l]|, G)]

알고리즘 설계

자료구조
- 세그먼트 트리: D[i]의 절댓값을 저장, 질의는 [l+1, r]의 GCD.
- 펜윅트리(BIT): 구간 가산을 두 점 갱신으로 저장하고 sum(l)로 현재 A[l] 복원.
연산 처리
- 갱신 T>0, [A,B]+=T:
  - BIT.rangeAdd(A,B,T)
  - D[A]+=T → 세그먼트 트리 점 갱신
  - D[B+1]-=T(단, B+1<=N) → 세그먼트 트리 점 갱신
- 질의 T=0, [A,B]:
  - base = A[A] + BIT.sum(A)
  - gdiff = gcd(D[A+1..B])
  - answer = gcd(|base|, gdiff)
올바름 근거(요지)
- 구간의 GCD는 첫 항과 인접 차분들의 GCD로 표현되며, 구간 덧셈은 차분 배열의 두 점만 변경하므로 세그먼트 트리로 빠르게 유지 가능.

복잡도

시간: \(O(\log N)\) per 연산
공간: \(O(N)\)

구현 (C++)

  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Fenwick {
    int n;
    vector<int64> bit;
    Fenwick(int n=0): n(n), bit(n+1, 0) {}
    void add(int idx, int64 delta){
        for(; idx<=n; idx+=idx&-idx) bit[idx] += delta;
    }
    void range_add(int l, int r, int64 delta){
        add(l, delta);
        if(r+1 <= n) add(r+1, -delta);
    }
    int64 sum(int idx) const {
        int64 s = 0;
        for(; idx>0; idx-=idx&-idx) s += bit[idx];
        return s;
    }
};

struct SegTreeGCD {
    int n;
    vector<int64> tree; // stores non-negative gcds
    SegTreeGCD(int n=0): n(n), tree(4*n+4, 0) {}
    static int64 gcdll(int64 a, int64 b){
        if(a<0) a = -a;
        if(b<0) b = -b;
        return std::gcd(a, b);
    }
    void build(const vector<int64>& diff, int node, int s, int e){
        if(s==e){
            tree[node] = llabs(diff[s]);
            return;
        }
        int m=(s+e)>>1, l=node<<1, r=l|1;
        build(diff, l, s, m);
        build(diff, r, m+1, e);
        tree[node] = gcdll(tree[l], tree[r]);
    }
    void build(const vector<int64>& diff){
        if(n>0) build(diff, 1, 1, n);
    }
    void point_set(int node, int s, int e, int idx, int64 val){
        if(s==e){
            tree[node] = llabs(val);
            return;
        }
        int m=(s+e)>>1, l=node<<1, r=l|1;
        if(idx<=m) point_set(l, s, m, idx, val);
        else point_set(r, m+1, e, idx, val);
        tree[node] = gcdll(tree[l], tree[r]);
    }
    void point_set(int idx, int64 val){
        point_set(1, 1, n, idx, val);
    }
    int64 range_gcd(int node, int s, int e, int l, int r) const {
        if(r<s || e<l) return 0;
        if(l<=s && e<=r) return tree[node];
        int m=(s+e)>>1, L=node<<1, R=L|1;
        int64 g1 = range_gcd(L, s, m, l, r);
        int64 g2 = range_gcd(R, m+1, e, l, r);
        return std::gcd(g1, g2);
    }
    int64 range_gcd(int l, int r) const {
        if(l>r) return 0;
        return range_gcd(1, 1, n, l, r);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if(!(cin >> N)) return 0;
    vector<int64> a(N+1);
    for(int i=1;i<=N;i++) cin >> a[i];

    // diff[1] = a[1], diff[i] = a[i] - a[i-1] for i>=2
    vector<int64> diff(N+1, 0);
    if(N>=1) diff[1] = a[1];
    for(int i=2;i<=N;i++) diff[i] = a[i] - a[i-1];

    SegTreeGCD seg(N);
    seg.build(diff);

    Fenwick fw(N); // holds only updates to reconstruct current a[i] = a[i]_init + fw.sum(i)

    int Q; cin >> Q;
    while(Q--){
        long long T; int A, B;
        cin >> T >> A >> B;
        if(A > B) swap(A, B);

        if(T == 0){
            int64 base = a[A] + fw.sum(A); // current a[A]
            if(A == B){
                cout << llabs(base) << '\n';
            }else{
                int64 gdiff = seg.range_gcd(A+1, B); // gcd of diff[A+1..B]
                int64 ans = std::gcd(llabs(base), gdiff);
                cout << llabs(ans) << '\n';
            }
        }else{
            // range add: update BIT and two points in diff/seg
            fw.range_add(A, B, T);

            diff[A] += T;
            seg.point_set(A, diff[A]);

            if(B+1 <= N){
                diff[B+1] -= T;
                seg.point_set(B+1, diff[B+1]);
            }
        }
    }
    return 0;
}