fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 17408 (C++) 수열과 쿼리 24
최초 업로드: 2025-11-19 14:33:18
최근 수정 시간: 2025-11-19 14:33:18
게시자: rlatjwls3333
카테고리: 백준
조회수: 6
# [Platinum IV] 수열과 쿼리 24 [문제 링크](https://www.acmicpc.net/problem/17408) ## 문제 설명 <p>길이가 N인 수열 A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>N</sub>이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오</p> <ul> <li><code>1 i v</code>: A<sub>i</sub>를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 10<sup>9</sup>)</li> <li><code>2 l r</code>: l ≤ i < j ≤ r을 만족하는 모든 A<sub>i</sub> + A<sub>j</sub> 중에서 최댓값을 출력한다. (1 ≤ l < r ≤ N)</li> </ul> <p>수열의 인덱스는 1부터 시작한다.</p> ## 입력 <p>첫째 줄에 수열의 크기 N이 주어진다. (2 ≤ N ≤ 100,000)</p> <p>둘째 줄에는 A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>N</sub>이 주어진다. (1 ≤ A<sub>i</sub> ≤ 10<sup>9</sup>)</p> <p>셋째 줄에는 쿼리의 개수 M이 주어진다. (2 ≤ M ≤ 100,000)</p> <p>넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.</p> ## 출력 <p>2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.</p> ## 풀이 세그먼트 트리를 구현할 때, pair로 제일 큰 값과 두 번째로 큰 값 두개를 리턴해주면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MAX = 100'000*4; int _size=1; pii arr[MAX]; pii makePair(pii a, pii b) { pii ret; ret.first = max(a.first, b.first); ret.second = max({min(a.first, b.first), a.second, b.second}); return ret; } void update(int i, int val) { i += _size/2; arr[i].first=val; while(i>1) { i>>=1; arr[i] = makePair(arr[i*2], arr[i*2+1]); } } pii query(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) { if(R<nodeL || nodeR<L) return {-1, -1}; if(L<=nodeL && nodeR<=R) return arr[nodeNum]; int mid = nodeL+nodeR>>1; return makePair(query(L, R, nodeNum*2, nodeL, mid), query(L, R, nodeNum*2+1, mid+1, nodeR)); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(_size<n) _size<<=1; _size<<=1; for(int i=_size/2;i<_size/2+n;i++) { cin >> arr[i].first; arr[i].second=-1; } for(int i=_size/2-1;i>0;i--) { arr[i] = makePair(arr[i*2], arr[i*2+1]); } int m; cin >> m; while(m--) { int a, b, c; cin >> a >> b >> c; if(a==1) { update(b-1, c); } else { pii ret = query(b-1, c-1); cout << ret.first + ret.second << '\n'; } } } ```