(9345) 디지털 비디오 디스크(DVDs)

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

단계별로 풀어보기

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

 

 

 

구간 [a,b]에 a부터 b까지의 수가 있는지를 판별해야 하는 문제.

수열에 중복되는 수가 없으므로, 구간 [a,b]의 최소값이 a, 최대값이 b라면 이 구간에는 a부터 b까지의 수가 전부 있다는 의미다.

이런 새그먼트 트리는 이미 이전 문제에서 구현해봤으므로 update 함수만 추가로 구현해주면 된다.

인덱스에 주의하자. 새그먼트 트리는 구현 편의 상 높은 확률로 1-base 인덱싱인데 문제에서 주어지는 DVD의 위치는 0-base 인덱싱으로 주어지기 때문이다.

 

 

 

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

void solve(){
  int n, k;
  
  cin >> n >> k;
  
  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++)  v[i]= i-1;
  
  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 update= [&](auto self, int s, int e, int node, int idx) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      segtree[node]= {v[s], v[s]};
    }else{
      self(self, s, s+(e-s)/2, node*2, idx);
      self(self, s+(e-s)/2+1, e, node*2+1, idx);
      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 {100000, -1};
    
    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<k;i++){
    int q, a, b;
    
    cin >> q >> a >> b;
    
    if(q==0){
      swap(v[a+1], v[b+1]);
      update(update, 1, n, 1, a+1);
      update(update, 1, n, 1, b+1);
    }else{
      auto res= query(query, 1, n, 1, a+1, b+1);
      
      cout << (res.first==a&&res.second==b ? "YES\n" : "NO\n");
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }
  
  return 0;
}