(1517) 버블 소트

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

단계별로 풀어보기

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

 

 

 

배열 내 어떤 수는 인덱스가 자신보다 크고 값이 자기보다 작은 수의 개수만큼 Swap이 발생한다. 이를 1~N번째 수에 대해 적용하는데 직접 구하면 O(N^2)이므로 당연히 시간초과고, 새그먼트 트리를 응용해 풀 수 있다.

새로운 배열을 하나 만드는데 이 배열의 x번째 값은 현재 탐색중인 수보다 배열의 x번째 수가 작다면 1, 아니라면 0이다.

배열을 값을 기준으로 정렬한 뒤 이 순서대로 원래 인덱스를 탐색한다고 하자. x번째 수의 인덱스가 y번이라면 Swap 횟수는 새로운 배열의 y+1~N번 인덱스의 구간합이다. 이 값을 더한 뒤 다음에 탐색할 수는 항상 x번째 수보다 크므로 y번째 배열의 값도 (0에서 1로) 업데이트한다.

만약 값이 같은 수가 있다면 Swap하지 않으므로 값이 같을 땐 인덱스가 앞쪽인 순서대로 탐색해야 한다. 앞쪽 값이 업데이트 되더라도 이후 탐색하는 수의 인덱스는 이 인덱스보다 뒤이므로 구간합에 포함되지 않는다.

 

참고로 새그먼트 트리를 안 쓰는 방식은 병합 정렬을 이용하는 방식인데, 앞에 있는 작은 값의 수를 구한다는 기본 아이디어는 같다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<pair<int, int>> v(n);
  vector<int> segtree(treesize);
  
  for(int i=0;i<n;i++){
    cin >> v[i].first;
    v[i].second= i+1;
  }
  
  sort(v.begin(), v.end());
  
  auto update= [&](auto self, int s, int e, int node, int idx) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      segtree[node]= 1;
    }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]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> int {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return lsum+rsum;
    }
  };
  
  long ans= 0;
  
  for(int i=0;i<n;i++){
    ans+= query(query, 1, n, 1, v[i].second+1, n);
    
    update(update, 1, n, 1, v[i].second);
  }
  
  cout << ans;
  
  return 0;
}