(5419) 북서풍

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

단계별로 풀어보기

49단계(스위핑) 3번째

 

 

 

북서풍을 타고 A섬에서 B섬으로 갈 수 있다면 A섬 x좌표보다 B섬 x좌표가 크거나 같고, A섬 y좌표보다 B섬 y좌표가 작거나 같다.

모든 섬을 x좌표 기준 오름차순, 같다면 y좌표 기준 내림차순으로 정렬한다.

정렬된 섬을 순서대로 탐색하면 항상 이전에 방문했던 점의 x좌표보다 크거나 같으므로 x좌표 조건은 생각하지 않고 y좌표 조건만 생각하면 된다. 새그먼트 트리에 지금까지 탐색한 y좌표에 존재하는 섬의 개수를 기록하고 현재 탐색한 섬의 y좌표보다 크거나 같은 섬의 개수를 세면 그것이 현재 섬에서 탐색 가능한 섬의 수가 된다(y좌표 기준 내림차순으로 정렬했으므로 x좌표 기준을 만족하는 섬들 중 y좌표가 큰 섬은 이미 전부 탐색 완료된 상태).

이때 좌표의 범위가 매우 크므로 y좌표를 기준으로 좌표 압축을 해주어야 한다.

 

 

 

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

long solve(){
  int n;
  long ans= 0;
  
  cin >> n;
  
  vector<pair<int,int>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  sort(v.begin(), v.end(), [](auto& A, auto& B){
    return A.second<B.second;
  });
  
  int ori_y= -1000000001, new_y= 0;
  for(auto& island:v){
    if(island.second==ori_y){
      island.second= new_y;
    }else{
      ori_y= island.second;
      island.second= ++new_y;
    }
  }
  
  int treesize= (1<<(((int)ceil(log2(new_y+1)))+1));
  vector<long> segtree(treesize);
  
  sort(v.begin(), v.end(), [](auto& A, auto& B){
    if(A.first!=B.first)  return A.first<B.first;
    return A.second>B.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]++;
    }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) -> long {
    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;
    }
  };
  
  for(auto& island:v){
    ans+= query(query, 1, new_y, 1, island.second, new_y);
    update(update, 1, new_y, 1, island.second);
  }
  
  return ans;
}

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