BOJ 17408 - 수열과 쿼리 24

관련 알고리즘과 함께 푼 수열과 쿼리 문제들을 쭉 포스팅 하려고 한다.

문제 링크 : https://www.acmicpc.net/problem/17408

문제 소개

• 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)

위의 두 가지 쿼리를 처리하는 것이 문제의 목표이다.

문제 풀이

기본적으로 노드의 변경과 최댓값 출력이므로 세그먼트 트리를 사용해야 한다. 하지만 그 전 단계와의 다른 점은 2번 쿼리에서 가장 큰 두개의 합을 출력해야 한다는 것이다. 구간 내에서 가장 큰 두 값을 찾는 것이 목표이고 이는 보통 두가지 풀이가 있다.

1번 풀이

세그먼트 트리의 노드에 최댓값과 그 위치를 같이 저장한다. 상위노드는 두 자식 노드중 값이 큰 노드를 그대로 가져오면 그 위치도 같이 저장할 수 있다. 2번 쿼리가 들어올 때 구간에서 최댓값과 그 위치를 찾을 수 있다. [l,r] 사이에서 얻은 최댓값의 위치가 x라고 했을 때 [l,x-1],[x+1,r] 구간에서 한 번 더 실행을 해주면 두번째로 큰 값을 찾을 수 있고 그 둘을 더해주면 된다. 

2번 풀이

훨씬 간단한 풀이이다. 세그먼트 트리의 노드에 최댓값과 두번째 최댓값을 둘 다 저장하는 것이다. 이때의 상위노드는 두 자식 노드의 4개의 값들 중 가장 큰 두 값을 저장하면 된다. 이런식으로 노드를 정하면 한 번에 문제를 해결할 수 있다. 보통 세그먼트 트리에서 노드에는 굉장히 많고 다양한 값들을 넣어서 신기한 테크닉을 많이 활용할 수 있다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
#define ff first
#define ss second
 
const int maxn=1e5+5;
pll tree[maxn*4];
ll arr[maxn];
ll n,m;
 
pll upt(ll idx, ll val, ll s ,ll e,ll nod)
{
    //printf("%lld %lld %lld %lld %lld\n",idx,val,s,e,nod);
    if(e<idx||s>idx) return tree[nod];
    if(s==e)
    {
        tree[nod].ff=val;
        tree[nod].ss=s;
        return tree[nod];
    }
    pll a=upt(idx,val,s,(s+e)/2,nod*2);
    pll    b=upt(idx,val,(s+e)/2+1,e,nod*2+1);
    if(a.ff>b.ff)
    {
        return tree[nod]=a;
    }
    else return tree[nod]=b;
}
 
pll sol(ll l ,ll r, ll s,ll e,ll nod)
{
    if(e<l||s>r) return {0,0};
    if(l<=s&&e<=r) return tree[nod];
    return max(sol(l,r,s,(s+e)/2,nod*2),sol(l,r,(s+e)/2+1,e,nod*2+1));
 
}
 
int main()
{
    ll n,i,j,k,l,m,a,b,c;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a);
        upt(i,a,1,n,1);
    }
    scanf("%lld",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a==1)
        {
            upt(b,c,1,n,1);
        }
        else
        {
            pll ansa=sol(b,c,1,n,1);
            pll ansb=max(sol(b,ansa.ss-1,1,n,1),sol(ansa.ss+1,c,1,n,1));
            printf("%lld\n",ansa.ff+ansb.ff);
        }
    }
 
}