[BOJ][C++] 백준 14428번: 수열과 쿼리 16 (Gold I)

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

 

문제

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

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai≤ 109)
셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)
넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

출력

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

 

풀이

[🏕️ ICPC Sinchon/Segment Tree] - [BOJ][C++] 백준 2357번: 최솟값과 최댓값 (Gold I)

[BOJ][C++] 백준 2357번: 최솟값과 최댓값 (Gold I)

위에서 최솟값을 구하는 세그먼트 트리를 응용한 버전이다

응용이래봤자.. 세그먼트트리에 값만 저장하던 기존 형식에서

pair 자료형을 이용해 인덱스와 값을 같이 저장하면 된다.

 

이때 값이 같은 경우도 고려해야하므로 

pair가 주어졌을 때 값과 인덱스를 비교해서 뭘 더 작은걸로 선택할지 구해주는 함수를 정의해주자

typedef pair<ll, ll> ci;

ci smaller(ci a, ci b) {
    if(a.second == b.second) {
        return a.first<b.first ? a : b;
    }
    return a.second<b.second ? a : b;
}

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ci;

const ll INF = 1000000001;

int n,m,i, sz;
vector<ci>segment;

ci smaller(ci a, ci b) {
    if(a.second == b.second) {
        return a.first<b.first ? a : b;
    }
    return a.second<b.second ? a : b;
}

// b번째 수를 c로 바꾼다
void updateSegment(ll i, ll v) {
    ll idx = i + sz - 1;
    
    segment[idx] = {i, v};
    
    while(idx!=1) {
        idx /= 2;
        segment[idx] = smaller(segment[idx*2], segment[idx*2 + 1]);
    }
}

// b부터 c까지의 구간합
ll getMin(ll b, ll c) {
    ll left = b + sz - 1;
    ll right = c + sz - 1;
    
    ci ans = {0, INF};
    
    while(left <= right) {
        if(left%2 == 1) {
            ans = smaller(segment[left], ans);
            left++;
        }
        left = left/2;

        if(right%2 == 0) {
            ans = smaller(segment[right], ans);
            right--;
        }
        right = right/2;
    }
    
    return ans.first;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	ll a,b,c;
	cin >> n;
	
	// 세그먼트 트리 정의
	sz = pow(2, floor(log2(4*n))-1);
	segment.assign(sz*2, {0,INF});
	for(ll i=1; i<=n; i++) {
	    cin >> a;
	    updateSegment(i, a);
	}
	
	// 쿼리 실행
	cin >> m;
	for(ll i=0; i<m; i++) {
	    cin >> a >> b >> c;
	    
	    if(a==1) { // update tree
	        updateSegment(b, c);
	    } else if(a==2) { // get sum
	        cout << getMin(b, c) << "\n";
	    }
	}
	
    return 0;
}