[백준/C++][수열과 쿼리 15(14427번)]

문제

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

14427번: 수열과 쿼리 15

Solve

min_index라는 함수를 만들어서 작은 수의 인덱스를 반환하고 만약 수가 같으면 작은 인덱스를 반환하는 함수를 작성한다.

그리고 세그먼트 트리를 구현하는데 리프노드에 수를 넣지 말고 인덱스를 넣어서 노드들 마다 인덱스가 들어가도록 한다.

query 1번일 경우는 update 함수를 돌려서 노드들을 바꿔준다.

query 2번은 tree[1]+1이 항상 답이기에 tree[1]+1를 출력해준다.

출력하고 입력은 printf, scanf사용하여야지 시간초과를 피할 수 있다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
vector<long long> tree;
vector<int> v;
int min_index(int x,int y){
    if(v[x] == v[y]){return min(x,y);}
    return v[x]<v[y] ? x:y;
}
long long init(int node,int start,int end){
    if(start == end){return tree[node] = start;}
    return tree[node] = min_index(init(node*2,start,(start+end)/2),init(node*2+1,(start+end)/2+1,end));
}
long long update(int node,int start,int end,int idx){
    if(start>idx ||end<idx||start == end){return tree[node];}
    return tree[node] = min_index(update(node*2,start,(start+end)/2,idx),update(node*2+1,(start+end)/2+1,end,idx));
}
int main(void){
    int N,M;
    cin >> N;
    int tree_size = (1<<(int)ceil(log2(N))+1);
    tree.resize(tree_size);
    v.resize(N);
    for(int i = 0;i<N;i++){scanf("%d",&v[i]);}
    init(1,0,N-1);
    cin >> M;
    for(int i = 0;i<M;i++){
        int q;
        scanf("%d",&q);
        if(q == 1){
            int a,b;
            scanf("%d%d",&a,&b);
            v[a-1] = b;
            update(1,0,N-1,a-1);
        }
        else{
            printf("%lld\n",tree[1]+1);
        }
    }
}