[BOJ 14427] 수열과 쿼리 15

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

14427번: 수열과 쿼리 15

 

- 문제 요약

 

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

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러 개인 경우에는 인덱스가 작은 것을 출력한다.

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

 

 

- 알고리즘 정리

 

세그먼트 트리로 해결한 문제입니다.

쿼리를 입력받을 때, 1인지 2인지에 따라 처리를 다르게 해 줬습니다.

나머지는 기본적인 세그먼트 트리를 구현할 때와 동일하게 풀었습니다.

 

 

- 코드 작성

 

#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(arr[a]==arr[b]){
		return (a<b?a:b);
	}
	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];
	}
	int mid=(start+end)/2;
	return tree[node]=mn(update(start,mid,node*2,idx),update(mid+1,end,node*2+1,idx));
}

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];
	}
	init(0,n-1,1);
	cin>>m;
	for(int i=0;i<m;i++){
		int q,idx,val;
		cin>>q;
		if(q==1){
			cin>>idx>>val;
			idx--;
			arr[idx]=val;
			update(0,n-1,1,idx);
		}
		else{
			cout<<tree[1]+1<<'\n';
		}
	}
}

코드 제출 결과