(2357) 최솟값과 최댓값

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

단계별로 풀어보기

44단계(세그먼트 트리 1) 3번째

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<int> v(n+1);
  vector<pair<int,int>> segtree(treesize);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      segtree[node]= {v[s], v[s]};
    }else{
      self(self, s, s+(e-s)/2, node*2);
      self(self, s+(e-s)/2+1, e, node*2+1);
      segtree[node].first= min(segtree[node*2].first, segtree[node*2+1].first);
      segtree[node].second= max(segtree[node*2].second, segtree[node*2+1].second);
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> pair<int, int> {
    if(r<s||e<l)  return {1000000001, 0};
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      auto lres= self(self, s, s+(e-s)/2, node*2, l, r);
      auto rres= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return {min(lres.first, rres.first), max(lres.second, rres.second)};
    }
  };
  
  init(init, 1, n, 1);
  
  for(int i=0;i<m;i++){
    int a, b;
    
    cin >> a >> b;
    
    auto res= query(query, 1, n, 1, a, b);
    
    cout << res.first << " " << res.second << "\n";
  }
  
  return 0;
}