[BOJ][백준]세그먼트 트리-17408번 수열과 쿼리 24

https://www.acmicpc.net/problem/17408

17408번: 수열과 쿼리 24

문제

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

• 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 10^9)
• 2 l r: l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서 최댓값을 출력한다. (1 ≤ l < r ≤ N)

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

입력

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

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

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

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

출력

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

 

 

---

 

구간의 가장 큰 값과 두번째로 큰 값을 구해 더하는 쿼리 문제입니다.

가장 쉬운 방법으로는 max값과 두 번째 max값을 node로 가지는 tree를 구성하면 문제를 풀 수 있습니다.

하지만 이 문제를 조금 다르게 풀 수 있습니다. 최댓값과 idx를 node를 구성하는

tree를 구성 한 후 쿼리를 2개로 잘라서 문제를 풀 수 있습니다.

예를 들어, 3 2 5 6 1 4 7 4 5라는 수열이 주어져 있고, 1~6 구간으로 쿼리가 주어졌을 때,

첫 번째로 그 구간의 최댓값과 그 위치를 구합니다. 이 쿼리 구간의 최댓값은 6이며 위치는 4입니다.

두 번째로 아까 얻은 위치를 idx라고 할 때, (1~idx-1) 구간과 (idx+1~6) 구간의 최댓값을 구하면 됩니다.

(1~3) 구간의 최댓값은 5이고, (5~6) 구간의 최댓값은 4가 되어 둘 중 높은 값인 5가 최댓값이 됩니다.

마지막으로 첫 번째와 두 번째의 값들을 서로 더하면 쿼리를 처리할 수 있습니다.

이를 토대로 코드를 구현해 봅시다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N=100000+2;
int N,M;
vector<int>v;

struct SEG_TREE
{
    int n;
    vector<pair<int,int>>tree;
    SEG_TREE(vector<int>&arr)
    {
        n=arr.size();
        tree.resize(n*4);
        init(arr,0,n-1,1);
    }
    pair<int,int> init(vector<int>&arr,int left,int right,int node)
    {
        if(left==right)return tree[node]={arr[left],left};
        int mid=(left+right)/2;
        pair<int,int>l=init(arr,left,mid,node*2),r=init(arr,mid+1,right,node*2+1);
        if(l.first>r.first)return tree[node]=l;
        else return tree[node]=r;
    }
    pair<int,int>update(int idx,int k){return update(idx,k,0,n-1,1);}
    pair<int,int>update(const int idx,const int k,int left,int right,int node)
    {
        if(idx<left||right<idx)return tree[node];
        if(left==right)return tree[node]={k,idx};
        int mid=(left+right)/2;
        pair<int,int>l=update(idx,k,left,mid,node*2),r=update(idx,k,mid+1,right,node*2+1);
        if(l.first>r.first)return tree[node]=l;
        else return tree[node]=r;
    }
    pair<int,int>query(int left,int right){return query(left,right,0,n-1,1);}
    pair<int,int>query(const int left,const int right,int nodeLeft,int nodeRight,int node)
    {
        if(nodeRight<left||right<nodeLeft)return {0,-1};
        if(left<=nodeLeft&&nodeRight<=right)return tree[node];
        int mid=(nodeLeft+nodeRight)/2;
        pair<int,int>l=query(left,right,nodeLeft,mid,node*2),r=query(left,right,mid+1,nodeRight,node*2+1);
        if(l.first>r.first)return l;
        else return r;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    v.resize(N);
    for(auto&i:v)cin>>i;
    SEG_TREE seg(v);
    cin>>M;
    while(M--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int a,b;
            cin>>a>>b;
            seg.update(a-1,b);
        }
        else
        {
            int l,r;
            //first Max,second Left Max,second Right Max
            pair<int,int>fMax,sLMax,sRMax;
            cin>>l>>r;
            fMax=seg.query(l-1,r-1);
            sLMax=seg.query(l-1,fMax.second-1);
            sRMax=seg.query(fMax.second+1,r-1);
            cout<<fMax.first+max(sLMax.first,sRMax.first)<<"\n";
        }
    }
}

node를 pair형을 사용해 값과 위치를 저장해 두었습니다. update과정에서 값만 바뀌지 위치가 바뀌지 않으므로

다음과 같이 쿼리를 잘 처리할 수 있습니다. 이렇게 위치와 값을 같이 저장해두는 세그먼트는 처음 작성해 보았는데

이를 활용할 수 있는 문제가 있는지 찾아봐야겠네요.