백준 17408 (C++) 수열과 쿼리 24

최초 업로드: 2025-11-19 14:33:18

최근 수정 시간: 2025-11-19 14:33:18

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 수열과 쿼리 24

[문제 링크](https://www.acmicpc.net/problem/17408)

## 문제 설명

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오

수열의 인덱스는 1부터 시작한다.

## 입력

첫째 줄에 수열의 크기 N이 주어진다. (2 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (2 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

## 출력

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

## 풀이
세그먼트 트리를 구현할 때, 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';
 }
 }
}
```