14438번 수열과 쿼리 17

 세그먼트 트리 기본 문제

 

 10868번 문제 + update만 해주면 된다.

 

#include <iostream>
#include <vector>
#include <limits.h>
#define MAX 100001
 
using namespace std;
 
int arr[MAX];
int N,M;
vector<int> answer;
 
int mininit(int start, int end, int node, int* mintree) {
    if (start == end) return mintree[node] = arr[start];
    int mid = (start + end) / 2;
    //재귀적으로 두 부분으로 나눈 뒤에 그 최솟값을 자기 자신으로 합니다.
    return mintree[node] = min(mininit(start, mid, node * 2, mintree),mininit(mid + 1, end, node * 2 + 1, mintree));
}
 
int minupdate(int start, int end, int node, int index, int* mintree){
    if(start>index || end<index) return mintree[node];
    if(start==end) return mintree[node]=arr[index];
    int mid = (start+end)/2;
    return mintree[node]= min(minupdate(start,mid,node*2,index,mintree),minupdate(mid+1,end,node*2+1,index,mintree));
}
 
int minquery(int start, int end, int node, int left, int right,int* mintree) {
    //범위 밖에 있는 경우
    if (left > end || right < start) return INT_MAX;
    //범위 안에 있는 경우
    if (left <= start && end <= right) return mintree[node];
    //그렇지 않다면 두 부분으로 나누어 최솟값을 구하기
    int mid = (start + end) / 2;
    return min(minquery(start, mid, node * 2, left, right, mintree), minquery(mid + 1, end, node * 2 + 1, left, right, mintree));
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> arr[i];
    }
    
    cin >> M;
    
    int size = M * 4;
    int* mintree = new int[size];
    
    mininit(0,N-1,1,mintree);
    
    for(int i=0;i<M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        
        if(a==1){
            arr[b-1]=c;
            minupdate(0,N-1,1,b-1,mintree);
        }
        else{
            int k=minquery(0,N-1,1,b-1,c-1,mintree);
            answer.push_back(k);
        }
    }
    
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << "\n";
    }
}