BOJ 25639 - 수열과 최대 상승 쿼리 (P1)

20240816 추가) 지금 보니 이 문제는 그냥 금광세그 기초 문제이다. 아래에 적혀있는 풀이는 금광 세그를 자력솔(!)한 것이다.

 

사용 알고리즘

Segment Tree

 

풀이

세그먼트 트리의 각 노드에는 3개의 값을 관리한다.

(1) 담당하는 구간의 최댓값 (N_max)

(2) 담당하는 구간의 최솟값 (N_min)

(3) 담당하는 구간의 최대 상승 값 (N_up)

 

(1), (2)는 G1짜리 간단한 문제이므로 생략한다. (3)을 어떻게 처리할지를 생각해야 하는데, 리프 노드면 구간이 1이므로 그냥 0이다.

그럼 구간 크기가 2 이상인 노드의 최대 상승 값은 어떻게 구할까? 바로 max(R_max - L_min, R_up, L_up)이다. 이때 L은 현재 노드의 왼쪽 자식에서의 값이고 R은 오른쪽 자식에서의 값이다.

이제 쿼리가 주어진 경우를 생각해보자.

리프노드는 귀찮아서 안그렸다.

대충 이런 세그먼트 트리가 있다고 치고, [3,8]에서 답을 구해야 한다고 하자.

그러면 세그먼트 트리 상에서는, [3,4]와 [5,8]에서 재귀 호출이 끝나게 될 것이다.

불편하게도, 루트노드가 약간 짤렸다

그럼 여기서 답은 어떻게 구할까? 당연히 max(3~4에서의 최대 상승 값, 5~8에서의 최대 상승값, 둘다 걸쳐있는 최대 상승값)일 것이다.

각 노드의 최대 상승값은 위에서 미리 구해놨으니 간단한데, 걸쳐 있는 최대 상승값은 어떻게 구할까? 위에서 한 방법대로 (5~8에서의 최댓값 - 3~4에서의 최솟값)을 구하면 될것이다. 그런데 구간이 이상하게 주어져서, 저렇게 [L,R]에 완전히 포함되는 노드가 많아지면 이렇게 일일이 구하는 방법은 TLE가 날 것이다. 따라서 다른 방법을 생각해야한다.....

 

 

 

 

는 사실 아니다. 왜냐면 세그먼트 트리에서 쿼리를 처리할 때, 구간에 완전히 포함되는 노드는 항상 O(logN)개기 때문이다. 애초에 세그먼트 트리가 빠르게 동작하는 이유도 저 이유이다. 따라서 O(logN)개의 노드를 2개씩 골라서 각각 최대 상승 값을 구해주면 되고, 쿼리에 O((logN)^2)만큼의 시간 복잡도로 해결할 수 있다. (O(logN)C2이므로)

 

사실 O(logN)에도 해결할 수 있다. 그냥 평소처럼 쿼리를 처리할때, L,R에서 바로 답을 구해주면 된다. 그런데 필자는 멍청하게 저렇게 풀었다. 사실 생각을 덜 해도 되는거니까 똑똑한걸 수도 있다(?).

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
#include <random>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll n, q;
struct segtree{
    struct Node{
        ll M=-1e18, m=1e18, up=0;
    };
    vector<Node> tree;
    segtree(): tree(404040) {}
    void upd(ll node, ll s, ll e, ll idx, ll diff){
        if(idx<s or e<idx)return;
        if(s==e){
            tree[node].M = diff;
            tree[node].m = diff;
            tree[node].up = 0;
        }
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff);
            upd(node*2+1,mid+1,e,idx,diff);
            tree[node].M = max(tree[node*2].M, tree[node*2+1].M);
            tree[node].m = min(tree[node*2].m, tree[node*2+1].m);
            tree[node].up = max({tree[node*2].up, tree[node*2+1].up, tree[node*2+1].M - tree[node*2].m});
        }
    }
    void upd(ll idx, ll diff){ upd(1,1,n,idx,diff); }
    void query(ll node, ll s, ll e, ll l, ll r, vector<Node> &v){	//v에 구간 노드들을 담는다. 이때 세그트리 특성상 왼쪽 구간부터 담긴다
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            v.push_back(tree[node]);
            return;
        }
        ll mid = s+e>>1;
        query(node*2,s,mid,l,r,v); query(node*2+1,mid+1,e,l,r,v);
    }
    ll get(ll l, ll r){
        vector<Node> v;
        query(1,1,n,l,r,v);
        ll ans = 0;
        for(int i = 0 ; i < v.size() ; i++){	//2개의 노드를 골라 최대 상승 값을 구한다
            ans = max(ans, v[i].up);
            for(int j = i+1 ; j < v.size() ; j++){
                ans = max(ans, v[j].M-v[i].m);
            }
        }
        return ans;
    }
} seg;
ll arr[101010];
int main(){
    fast;
    cin>>n;
    for(int i = 1 ; i <= n ; i++){
        cin>>arr[i];
        seg.upd(i,arr[i]);
    }
    cin>>q;
    while(q--){
        ll a,b,c; cin>>a>>b>>c;
        if(a==1){
            seg.upd(b,c);
        }
        else{
            cout<<seg.get(b,c)<<"\n";
        }
    }
}