[BOJ 14428] 수열과 쿼리 16

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

14428번: 수열과 쿼리 16

 

- 문제 요약

 

길이가 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 ≤ v ≤ 109)

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

 

 

- 알고리즘 정리

 

수열과 쿼리 15번 문제의 변형 느낌입니다.

mn 함수를 만들어서 인덱스 2개를 입력받고, 범위를 벗어날 시 -1을 리턴해줍니다.

범위 안이라면 현재 노드의 값을 리턴해줍니다.

=> 값이 작은 인덱스 리턴 / 값이 같은 경우 작은 인덱스 리턴

 

 

- 코드 작성

 

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

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

int mn(int a,int b){
	if(a==-1){
		return b;
	}
	if(b==-1){
		return a;
	}
	if(arr[a]==arr[b]){
		return a<b?a:b;
	}
	else{
		return arr[a]<=arr[b]?a:b;
	}
}

int init(int start,int end,int node){
	if(start==end){
		return tree[node]=start;
	}
	int mid=(start+end)/2;
	return tree[node]=mn(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||start==end){ 
		return tree[node];
	}
	if(start==end){
		return tree[node];
	}
	int mid=(start+end)/2;
	return tree[node]=mn(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 -1;
	}
	if(left<=start&&end<=right){
		return tree[node];
	}
	int mid=(start+end)/2;
	return mn(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';
		}
	}
}

코드 제출 결과