[BOJ 14438] 수열과 쿼리 17

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

14438번: 수열과 쿼리 17

 

- 문제 요약

 

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

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 출력한다. (1 ≤ i ≤ j ≤ N)

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

 

 

- 알고리즘 정리

 

수열과 쿼리 16번과 비슷한 문제입니다.

1번 쿼리는 16번 문제와 동일하게 처리하고, 2번 쿼리가 들어왔을 때 최솟값을 출력해 주면 됩니다.

(16번 문제는 최솟값이 아니라 최솟값의 인덱스를 출력)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100000
int n,arr[MAX+1],m,tree[MAX*4+1];

int init(int start,int end,int node){
	if(start==end){
		return tree[node]=arr[start];
	}
	int mid=(start+end)/2;
	return tree[node]=min(init(start,mid,node*2),init(mid+1,end,node*2+1));
}

int update(int start,int end,int node,int idx){
	if(idx<start||idx>end){ 
		return tree[node];
	}
	if(start==end){
		return tree[node]=arr[idx];
	}
	int mid=(start+end)/2;
	return tree[node]=min(update(start,mid,node*2,idx),update(mid+1,end,node*2+1,idx));
}

int query(int start,int end,int node,int left,int right){
	if(start>right||end<left){
		return INT_MAX;
	}
	if(left<=start&&end<=right){
		return tree[node];
	}
	int mid=(start+end)/2;
	return min(query(start,mid,node*2,left,right),query(mid+1,end,node*2+1,left,right));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	init(1,n,1);
	cin>>m;
	for(int i=0;i<m;i++){
		int q,idx,val,aa,bb;
		cin>>q;
		if(q==1){
			cin>>idx>>val;
			arr[idx]=val;
			update(1,n,1,idx);
		}
		if(q==2){
			cin>>aa>>bb;
			cout<<query(1,n,1,aa,bb)<<'\n';
		}
	}
}

코드 제출 결과