(12899) 데이터 구조

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

단계별로 풀어보기

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

 

 

 

가능한 x의 범위가 200만이므로, 직접 관리하는 대신 카운팅 정렬 방식으로 200만개의 배열을 관리하면 된다. 배열의 값은 해당 인덱스에 해당하는 수가 S에 들어있는 개수를 의미한다.

X번째로 작은 수를 구할 땐 이분탐색을 이용하면 된다. 왼쪽 절반 구간의 부분합이 X 이하라면 해당 구간에 존재하는 수가 X개보다 적거나 같다는 의미이므로 왼쪽 절반에서 탐색하고, 아니라면 오른쪽 절반에서 탐색한다.

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define SIZE 2000000

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int treesize= (1<<(((int)ceil(log2(SIZE+1)))+1));
  vector<long> v(SIZE+1), segtree(treesize);
  
  auto update= [&](auto self, int s, int e, int node, int idx, int val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      segtree[node]+= val;
    }else{
      self(self, s, s+(e-s)/2, node*2, idx, val);
      self(self, s+(e-s)/2+1, e, node*2+1, idx, val);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int x) -> int {
    if(s==e)  return s;
    
    int lcnt= segtree[node*2];
    
    if(x<=lcnt)  return self(self, s, s+(e-s)/2, node*2, x);
    else  return self(self, s+(e-s)/2+1, e, node*2+1, x-lcnt);
  };
  
  int n;
  
  cin >> n;
  
  for(int i=0;i<n;i++){
    int t, x;
    
    cin >> t >> x;
    
    if(t==1){
      v[x]++;
      update(update, 1, SIZE, 1, x, 1);
    }else{
      int res= query(query, 1, SIZE, 1, x);
      
      cout << res << "\n";
      
      v[res]--;
      update(update, 1, SIZE, 1, res, -1);
    }
  }
  
  return 0;
}