백준 33007 - Greatest of the Greatest Common Divisors#

핵심 아이디어#

오프라인 쿼리 방식으로, r을 순차적으로 증가시키면서 r을 새롭게 포함시킬 때 해당 인덱스 r과 어떤 인덱스 l을 추가하면 어떤 gcdVal을 얻을 수 있는 지를 미리 저장해 놓았다가 이를 포함시킨다.
그리고 query의 오른쪽 끝이 r인 쿼리들에 대해서 정답을 업데이트 시켜준다.

풀이#

1. 소인수 분해를 전처리를 해준다.
   수의 개수와 수의 크기가 모두 최대 $10^5$ 이므로 총 $10^{7.5}$ 만에 모든 수의 소인수분해를 할 수 있다.
   divs[x] := { x로 나뉘어지는 모든 수들의 인덱스 } 형식으로 저장한다.
2. 위 전처리 결과를 이용해서 숫자 i를 소인수 분해로 갖는 수들의 목록을 얻을 수 있다.
   이때 이 수들에 대한 모든 쌍을 볼 필요 없이, 인접한 쌍 (l,r)끼리만 확인하면 된다. 왜냐하면 이 중 어느 2개의 수만 쿼리가 포함하면 숫자 i를 gcd로 가질 수 있기 때문이다.
   따라서 가장 가까운 두 쌍에 대해서만 pre[r].emplace_back(l, i) 이런 식으로 저장해주면 된다.
3. 쿼리도 마찬가지로 queries[r].emplace_back(l, i) 이런 식으로 저장해준다. 여기서 i는 쿼리 번호이다. 오프라인 쿼리 방식으로 처리해줄 것이다.
   1. 이제 모든 r을 순차적으로 증가시키면서 세그먼트 트리를 업데이트 시켜준다.
      for(auto [l, gcdVal]: pre[r]) 이런 식으로 r을 포함시켰을 때, 어떤 l을 포함하면 어떤 gcdVal을 얻을 수 있는 지를 세그먼트 트리에 업데이트 시켜준다.
   2. 쿼리도 for(auto [l, query_num]: queries[r]) 이런 식으로 쿼리의 범위 끝이 r인 쿼리들에 대한 답을 업데이트 해준다.

코드#

1#include <bits/stdc++.h>  
2  
3#define endl "\n"  
4#define all(v) (v).begin(), (v).end()  
5#define all1(v) (v).begin()+1, (v).end()  
6#define For(i, a, b) for(int i=(a); i<(b); i++)  
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)  
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)  
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)  
10#define ft first  
11#define sd second  
12  
13using namespace std;  
14using ll = long long;  
15using lll = __int128_t;  
16using ulll = __uint128_t;  
17using ull = unsigned long long;  
18using ld = long double;  
19using pii = pair<int, int>;  
20using pll = pair<ll, ll>;  
21using ti3 = tuple<int, int, int>;  
22using tl3 = tuple<ll, ll, ll>;  
23  
24template<typename T> using ve = vector<T>;  
25template<typename T> using vve = vector<vector<T>>;  
26  
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }  
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }  
29  
30const int INF = 987654321;  
31const int INF0 = numeric_limits<int>::max();  
32const ll LNF = 987654321987654321;  
33const ll LNF0 = numeric_limits<ll>::max();  
34  
35class Segment {  
36public:  
37    vector<int> tree; //tree[node] := a[start ~ end] 의 합  
38  
39    Segment() {}  
40    Segment(int size) {  
41        this->resize(size);  
42    }  
43    void resize(int size) {  
44        size = (int) floor(log2(size)) + 2;  
45        size = pow(2, size);  
46        tree.resize(size, 1);  
47    }  
48    int query(int node, int start, int end, int left, int right) {  
49        if(right < start || end < left) return 1;  
50        if(left <= start && end <= right) return tree[node];  
51        return max(query(node * 2, start, (start + end) / 2, left, right),  
52                   query(node * 2 + 1, (start + end) / 2 + 1, end, left, right));  
53    }  
54    void update(int node, int start, int end, int index, int value) {  
55        if(index < start || end < index) return;  
56        if(start == end) ckmax(tree[node], value);  
57        else {  
58            update(node * 2, start, (start + end) / 2, index, value);  
59            update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);  
60            tree[node] = max(tree[2*node], tree[2*node+1]);  
61        }  
62    }  
63};  
64  
65const int mxn = 1e5+1;  
66int n, q;  
67ve<int> a;  
68vve<int> divs(mxn);  
69vve<pii> pre, queries;  
70ve<int> ans;  
71  
72ll gcd(ll a, ll b) {  
73    if(b == 0) return a;  
74    return gcd(b, a%b);  
75}  
76  
77void solve() {  
78    cin >> n;  
79    a = ve<int>(n+1);  
80    pre = vve<pii>(n+1);  
81    queries = vve<pii>(n+1);  
82    FOR(i,1,n) cin >> a[i];  
83  
84    // 모든 소인수들에 대해서 어떤 a[인덱스]를 나눌 수 있는지를 모두 저장. 즉, 미리 소인수분해를 해 놓는다.  
85    FOR(i,1,n) {  
86        for(int j=1; j*j<=a[i]; j++) {  
87            if(a[i]%j == 0) {  
88                divs[j].emplace_back(i);  
89                if(j*j != a[i]) divs[a[i]/j].emplace_back(i);  
90            }  
91        }  
92    }  
93  
94    // 모든 i에 대하여 i로 나눠지는 l,r (여기서 l,r은 인접한 애들)을 저장해준다.  
95    FOR(i,1,mxn) {  
96        for(int j=1; j<divs[i].size(); j++) {  
97            int l=divs[i][j-1], r=divs[i][j];  
98            if (gcd(a[l], a[r]) == i) pre[r].emplace_back(l,i);  
99        }  
100    }  
101  
102    cin >> q;  
103    ans = ve<int>(q+1, 1);  
104    FOR(i,1,q) {  
105        int l, r; cin >> l >> r;  
106        queries[r].emplace_back(l,i);  
107    }  
108  
109  
110    Segment seg(n);  
111    // 1 ~ r 에 대한 수들만 처리하고, 그에 대한 쿼리만 순차대로 처리해준다.  
112    FOR(r,1,n) {  
113        // pre[r] 정보들을 세그먼트 트리에 업데이트시켜준다.  
114        for(auto [l, gcdVal]: pre[r]) {  
115            seg.update(1,1,n,l,gcdVal);  
116        }  
117  
118        // r이 r인 쿼리들에 대한 정답을 계산해준다.  
119        for(auto [l, qn]: queries[r]) {  
120            ckmax(ans[qn], seg.query(1,1,n,l,r));  
121        }  
122    }  
123  
124    FOR(i,1,q) cout << ans[i] << endl;  
125}  
126  
127int main(void) {  
128    ios_base::sync_with_stdio(false);  
129    cin.tie(nullptr);  
130    cout.tie(nullptr);  
131  
132    int TC=1;  
133//    cin >> TC;  
134    FOR(tc, 1, TC) {  
135//        cout << "Case #" << tc << ": ";  
136        solve();  
137    }  
138  
139  
140    return 0;  
141}

참고#

• 구사과님의 깃허브