백준 14427 수열과 쿼리 15

요즘 세그먼트 트리 문제 푸는 데에 집중하는 듯..

원래는 입력 2에 대한 쿼리 수행하는 query함수 이용하려 했는데 생각해보니 그냥 Tree[1] 접근하면 되는 문제였다. (수열 전체에서 크기가 가장 작은 값의 인덱스를 출력하는 것이기 때문에 left, right가 무의미해지기 때문)

#include <iostream>
#include <vector>
using namespace std;

vector<long long> arr;
vector<int> Tree;

struct cmd{
  int op;
  int idx;
  long long v; 
};
vector<cmd> CMD;

int N, M;

void input(){
  cin >> N;
  arr.resize(N);
  Tree.resize(N*4,0);
  for(int i=0; i<N; i++){
    cin >> arr[i];
  }
  cin >> M;
  for(int i=0; i<M; i++){
    int op;
    cin >> op;
    if(op==2){
      CMD.push_back({op, -1, -1});
    } 
    else if(op==1){
      int idx;
      long long v;
      cin >> idx >> v;
      CMD.push_back({op, idx, v});
    }
  }
}

int minIndex(int x, int y){
  if(x<0) return y;
  if(y<0) return x;
  if(arr[x]==arr[y]) return x<=y ? x:y;
  else return arr[x]<=arr[y]? x:y;
}

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

int update(int start, int end, int node, int index){
  if(start > index || index > end) return Tree[node];
  if(start == end) return Tree[node];
  int mid = (start + end)/2;
  return Tree[node] = minIndex(update(start, mid , node * 2, index), update(mid + 1, end, node * 2 + 1, index));
}

void solve(){
  
  for(int i = 0; i<M; i++){
    int op;
    op = CMD[i].op;
    if(op == 2){
      cout << Tree[1] + 1<<"\n";
    }
    else if(op ==1){
      int idx;
      long long v;
      idx = CMD[i].idx;
      v = CMD[i].v;
      arr[idx-1] = v;
      update(0, N-1, 1, idx-1) ;
    }
  }
}
int main() {
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  input();
  init(0, N-1 ,1);
  solve();
  return 0;
}