[BOJ 12858] Range GCD

https://www.acmicpc.net/problem/12858

12858번: Range GCD

Tag : segment tree

 

문제요약

구간 업데이트(덧셈)가 있을 때 쿼리마다 구간의 gcd를 구하라.

 

풀이

a > b일 때 gcd(a, b) = gcd(a, a - b)임이 잘 알려져있습니다. 

따라서 gcd(A[l], ... , A[r]) = gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])이 성립합니다.

세그먼트 트리의 각 노드에서 gcd(A[l + 1] - A[l], ... , A[r] - A[r - 1])을 관리한다면 구간 업데이트가 실행됐을 때

실제로 값이 바뀌는 부분은 경계의 두 부분뿐입니다. 

 

A[l]을 관리하는 range update point query 트리 하나와

gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])을 관리하는 트리 하나를 관리하면 

쿼리마다 \(O(logN)\)에 답을 구할 수 있습니다. (gcd구하는 시간은 고려 안함)

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, q;
int a[101010];
ll diff[404040];
ll ps[101010];

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

void init(int node, int s, int e) {
    if(s == e) diff[node] = a[s + 1] - a[s];
    else {
        init(node * 2, s, (s + e) / 2);
        init(node * 2 + 1, (s + e) / 2 + 1, e);
        diff[node] = GCD(diff[node * 2], diff[node * 2 + 1]);
    }
}

ll diffqry(int node, int s, int e, int l, int r) {
    if(s > r or e < l) return 0;
    if(l <= s and e <= r) return diff[node];
    int m = (s + e) / 2;
    return GCD(diffqry(node * 2, s, m, l, r), diffqry(node * 2 + 1, m + 1, e, l, r));
}

void diffupd(int node, int s, int e, int i, ll x) {
    if(i < s or i > e) return;
    if(s == e) diff[node] += x;
    else {
        int m = (s + e) / 2;
        diffupd(node * 2, s, m, i, x);
        diffupd(node * 2 + 1, m + 1, e, i, x);
        diff[node] = GCD(diff[node * 2], diff[node * 2 + 1]);
    }
}

ll qry(int i) {
    ll ret = 0;
    while(i > 0) ret += ps[i], i -= i & -i;
    return ret;
}

void upd(int i, ll x) { while(i <= n) ps[i] += x, i += i & -i; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        upd(i, a[i]); upd(i + 1, -a[i]);
    }
    init(1, 1, n);
    cin >> q;
    while(q--) {
        int t, x, y; cin >> t >> x >> y;
        if(t == 0) {
            ll p = qry(x);
            ll q = abs(diffqry(1, 1, n, x, y - 1));
            cout << GCD(p, q) << endl;
        } else {
            diffupd(1, 1, n, x - 1, t);
            diffupd(1, 1, n, y, -t);
            upd(x, t); upd(y + 1, -t);
        }
    }
}