백준 14428 수열과 쿼리 16

최소 인덱스 찾는 세그먼트 트리

#include <iostream>
#include <vector>
using namespace std;
int N, M;

vector<long long> arr;
vector<long long> Tree;
vector<pair<int, pair<int, long>>> query;

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, a;
    long long b;
    cin >> op >> a >> b;
    query.push_back({op, {a,b}});
  }
  
}

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 solveQuery(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 minIndex(solveQuery(start, mid, node * 2, left, right), solveQuery(mid + 1, end, node * 2 + 1, left, right));
}

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;
  Tree[node] = minIndex(update(start, mid, node * 2, index), update(mid+1, end, node * 2 + 1, index));
  return Tree[node];
}

void solve(){
  for(int i = 0; i < M ; i++) {
    int op, idx;
    op = query[i].first;
    idx = query[i].second.first;
    if(op == 1){
      long long v = query[i].second.second;
      arr[idx-1] = v;
      update(0, N-1, 1, idx-1);
    }
    else if(op == 2){
      int right = query[i].second.second;
      cout << solveQuery(0, N-1, 1, idx-1, right-1) + 1 <<"\n";
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  init(0, N-1, 1);
  solve();
  return 0;
  
}