Range GCD (백준 12858)

안녕하세요. 오늘은 GCD값을 구할 거예요.

문제

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

아이디어

gcd의 성질부터 알아봅시다.
gcd(a,b,c,d,....)는 gcd(a,b-a,c-b,d-c,....)와 동일합니다.
즉, gcd값을 알려면 arr의 값과 arr의 차의 값을 알아야합니다. 여기서 주의할 점은 arr는 tree값이 합으로 저장이 되지만 arr의 차는 tree값이 gcd로 저장이 됩니다. 바로바로 꺼내쓸 수 있게 말이죠.

이때 수를 바꾸는 쿼리가 있으면 arr는 구간이 바뀌므로 lazyprop을 써야합니다. 하지만 arr의 차는 바뀌는 부분이 딱 두 군데 있으므로 그냥 함수 두번 써주면 됩니다.

이제 세그트리 두개를 구현만 잘하면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[404040] = { 0 }, lazy[404040] = { 0 }, arr[101010] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = arr[s];
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
void pp(ll s, ll e, ll node)
{
    if (lazy[node])
    {
        tree[node] += lazy[node];
        if (s != e)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
ll find(ll s, ll e, ll node, ll idx) //idx번지에 있는 값 찾기
{
    pp(s, e, node);
    if (e < idx || idx < s) return 0;
    if (s == e) return tree[node];
    ll mid = (s + e) / 2;
    return find(s, mid, node * 2, idx) + find(mid + 1, e, node * 2 + 1, idx);
}
void change(ll s, ll e, ll node, ll l, ll r, ll val)
{
    pp(s, e, node);
    if (e < l || r < s) return;
    if (l <= s && e <= r)
    {
        lazy[node] = val;
        pp(s, e, node);
        return;
    }
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, l, r, val);
    change(mid + 1, e, node * 2 + 1, l, r, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll GCD_tree[404040] = { 0 }, GCD_arr[404040];
ll gcd(ll x, ll y) { return ((y) ? gcd(y, x % y) : x); }
ll GCD_init(ll s, ll e, ll node)
{
    if (s == e) return GCD_tree[node] = GCD_arr[s];
    ll mid = (s + e) / 2;
    return GCD_tree[node] = gcd(GCD_init(s, mid, node * 2), GCD_init(mid + 1, e, node * 2 + 1));
}
ll GCD(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return GCD_tree[node];
    ll mid = (s + e) / 2;
    return gcd(GCD(s, mid, node * 2, l, r), GCD(mid + 1, e, node * 2 + 1, l, r));
}
void GCD_change(ll s, ll e, ll node, ll idx, ll val) //idx번지에 있는 값을 val만큼 바꾸기
{
    if (e < idx || idx < s) return;
    if (s == e)
    {
        GCD_tree[node] += val;
        return;
    }
    ll mid = (s + e) / 2;
    GCD_change(s, mid, node * 2, idx, val);
    GCD_change(mid + 1, e, node * 2 + 1, idx, val);
    GCD_tree[node] = gcd(GCD_tree[node * 2], GCD_tree[node * 2 + 1]);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, Q, t, a, b;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        if (i >= 2) GCD_arr[i - 1] = arr[i] - arr[i - 1];
    }
    init(1, N, 1); GCD_init(1, N, 1);

    cin >> Q;
    for (i = 1; i <= Q; i++)
    {
        cin >> t >> a >> b;
        if (t == 0)
        {
            if (a == b) cout << find(1, N, 1, a);
            else cout << abs(gcd(find(1, N, 1, a), GCD(1, N, 1, a, b - 1)));
            cout << "\n";
        }
        else
        {
            change(1, N, 1, a, b, t);
            GCD_change(1, N, 1, a - 1, t);
            GCD_change(1, N, 1, b, -t);
        }
    }
}

감사합니다.