백준12858 Range GCD

작성일 | In

문제 링크

  • http://icpc.me/12858

사용 알고리즘

  • Segment Tree
  • Lazy Propagation

시간복잡도

  • O(Q log N)

풀이

gcd(a, b, c, d, e, …) = gcd(a, abs(b-a), abs(c-b), abs(d-c), abs(e-d), …)와 동일합니다.
그러므로 어떤 구간 [l, r]에 전부 v를 더해주더라도 구간의 양 끝의 변화( l-1과 l의 차이, r과 r+1의 차이 )만 봐주면 됩니다.

원소를 관리해주는 Segment Tree는 구간 업데이트가 들어오기 때문에 Lazy Propagation을 이용해 구현해주고, gcd를 관리해주는 Segment Tree는 한 번의 쿼리마다 두 개의 지점에서만 업데이트하므로 Lazy Propagation을 사용할 필요가 없습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll f(ll a, ll b){
	if(a == 0) return b;
	if(b == 0) return a;
	return __gcd(a, b);
}

struct LazySeg{
	ll tree[404040];
	ll lazy[404040];

	void pro(int node, int s, int e){
		if(!lazy[node]) return;
		tree[node] += (e-s+1) * lazy[node];
		if(s != e){
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0;
	}

	void update(int node, int s, int e, int l, int r, ll v){
		pro(node, s, e);
		if(r < s || e < l) return;
		if(l <= s && e <= r){
			tree[node] += (e-s+1) * v;
			if(s ^ e){
				lazy[node*2] += v;
				lazy[node*2+1] += v;
			}
			return;
		}
		int m = s + e >> 1;
		update(node*2, s, m, l, r, v);
		update(node*2+1, m+1, e, l, r, v);
		tree[node] = tree[node*2] + tree[node*2+1];
	}

	ll query(int node, int s, int e, int x){
		pro(node, s, e);
		if(x < s || e < x) return 0;
		if(s == e) return tree[node];
		int m = s + e >> 1;
		return query(node*2, s, m, x) + query(node*2+1, m+1, e, x);
	}

	void update(ll a, ll b, ll c){
		update(1, 1, 100000, a, b, c);
	}

	ll query(int x){
		return query(1, 1, 100000, x);
	}
}bit;

struct Seg{
	int tree[404040];
	int bias;

	Seg(){
		for(bias=1; bias<101010; bias<<=1);
	}

	void update(int x, int v){
		tree[x += bias] = v;
		while(x >>= 1){
			tree[x] = f(tree[x << 1], tree[x << 1 | 1]);
		}
	}

	ll query(int l, int r){
		l += bias, r += bias;
		int ret = 0;
		while(l < r){
			if(l & 1) ret = f(ret, tree[l++]);
			if(~r & 1) ret = f(ret, tree[r--]);
			l >>= 1, r >>= 1;
		}
		if(l == r) ret = f(ret, tree[r]);
		return ret;
	}
}seg;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n; i++){
		ll t; cin >> t;
		bit.update(i, i, t);
	}
	for(int i=1; i<n; i++){
		ll now = bit.query(i) - bit.query(i+1);
		seg.update(i, abs(now));
	}

	int m; cin >> m;
	while(m--){
		int op, a, b; cin >> op >> a >> b;
		if(op == 0){
			ll now = seg.query(a, b-1);
			now = f(now, bit.query(a));
			cout << now << "\n";
		}else{
			bit.update(a, b, op);
			ll now = bit.query(a-1) - bit.query(a);
			seg.update(a-1, abs(now));
			now = bit.query(b) - bit.query(b+1);
			seg.update(b, abs(now));
		}
	}
}