수열과 쿼리 24 [BOJ 17408]

세그먼트 트리 응용을 막 시작한 사람들에게 추천하는 문제이다. 세그먼트 트리 배우고 얼마 지나지 않아서는 최댓값/최솟값/구간 합 말고는 세그먼트 트리를 떠올리기 어려운데, 더 심화된 응용의 세그먼트 트리를 쓰려면 이런 간단한 응용들로부터 시작하여야 한다고 생각한다.

 

문제 요약

길이 10만 이하의 수열 A에서 2가지 쿼리를 수행한다.

1 i v : A[i]를 v로 바꾼다

2 l r : l<=i<j<=r을 만족하는 모든 A[i]+A[j] 중 최댓값을 출력한다.

 

사용 알고리즘

세그먼트 트리

 

풀이

어떤 구간에서 서로 다른 두 수를 뽑아 가장 크게 만드려면 그 구간에서 가장 큰 숫자 2개를 뽑아야한다는 사실을 알 수 있다. 즉, 어떤 구간에서의 최댓값과 2번째로 큰 값을 알아야하는 문제이다.

구간의 최댓값을 구하는 것은 이미 할 줄 안다. 그렇다면 구간의 2번째 최댓값은 어떻게 구해야할까?

우리는 세그먼트 트리의 두 노드를 합치는 것을 지금까지는 상당히 간단한 연산으로 처리하였다. 예를 들어, 최솟값 쿼리면 i*2번 노드와 i*2+1번 노드의 값 중 작은 값을 반환하였다. 이 과정에 min 연산 1번을 통해 이루어지는 이유는 현재 구간의 최솟값이 양쪽 구간의 최솟값 중 작은 값과 같기 때문이다. 이번에는 각 노드의 가장 큰 두 개의 값을 각각 mx1, mx2라고 하자. 그렇다면 양쪽 구간에서 총 4개의 값이 모일 것이고, 이 4개의 값 중 가장 큰 두 개의 값을 새로운 노드의 mx1, mx2가 될 것이다. 이를 pair 배열에 저장하면 조금 더 쉽게 구현할 수 있다.

또한 필자는 구현 중에 mer이라는 함수를 사용했는데, 이는 '병합하다'라는 뜻의 영어 단어 merge에서 따온 것이다. 더욱 어려운 문제로 가면 merge 과정 자체에서 고려해 주어야할 것이 많기 때문에 자주 보게 될 것이다. 해당 문제에서는 4개의 값 중 2개의 값을 추려내는 과정을 mer 함수에 담았다.

 

코드

#include<bits/stdc++.h>
#define SIZE 100010
using namespace std;
pair<int,int>seg[4*SIZE];
int N,Q,A[SIZE];
pair<int,int>mer(pair<int,int>x,pair<int,int>y)
{
    vector<int>v;
    v.push_back(x.first);
    v.push_back(x.second);
    v.push_back(y.first);
    v.push_back(y.second);
    sort(v.begin(),v.end());
    return {v[3],v[2]};
}
void init(int l,int r,int node)
{
    if(l>r)return;
    if(l==r){
        seg[node]={A[l],-1};
        return;
    }
    int mid=l+r>>1;
    init(l,mid,node<<1);
    init(mid+1,r,(node<<1)+1);
    seg[node]=mer(seg[node<<1],seg[(node<<1)+1]);
}
void update(int l,int r,int node,int s,int w)
{
    if(l>r||l>s||r<s)return;
    if(l==s&&r==s){
        seg[node]={w,-1};
        return;
    }
    int mid=l+r>>1;
    update(l,mid,node<<1,s,w);
    update(mid+1,r,(node<<1)+1,s,w);
    seg[node]=mer(seg[node<<1],seg[(node<<1)+1]);
}
pair<int,int>query(int l,int r,int node,int s,int e)
{
    if(l>r||l>e||r<s)return {-1,-1};
    if(s<=l&&r<=e)return seg[node];
    int mid=l+r>>1;
    return mer(query(l,mid,node<<1,s,e),query(mid+1,r,(node<<1)+1,s,e));
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    init(1,N,1);
    for(cin>>Q;Q--;){
        int tc,s,e;scanf("%d %d %d",&tc,&s,&e);
        if(tc-1){
            pair<int,int>z=query(1,N,1,s,e);
            printf("%d\n",z.first+z.second);
        }
        else update(1,N,1,s,e);
    }
}