(11012) Egg

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

단계별로 풀어보기

49단계(스위핑) 6번째

 

 

 

이 문제를 푸는 법은 크게 세 가지로 나눌 수 있다.

1) 영속성 새그먼트 트리(PST)를 이용하는 방법: x좌표의 달걀의 개수를 새그먼트 트리로 관리하고 이를 y좌표마다 누적시켜 새그먼트 트리 배열을 만들면 직사각형 내 달걀을 누적합으로 구할 수 있다. 메모리 초과가 나므로 PST를 써서 관리하면 된다.

2) 머지 소트 트리(MST)를 이용하는 방법: x좌표를 기준으로 하는 어떤 구간에 존재하는 모든 달걀을 y좌표를 기준으로 정렬하여 관리한다. x좌표 구간이 주어진 직사각형 범위 내인 모든 노드에 대해 이분 탐색으로 y좌표가 범위 내인 달걀을 구해 더하면 된다.

3) 스위핑 + 새그먼트 트리를 이용하는 방법

 

스위핑 단계이므로 3번으로 풀어보겠다. 퍼레이드 구역이 아닌 달걀을 기준으로 생각하면, 어떤 달걀이 받아진 횟수는 이 달걀의 좌표를 포함하는 퍼레이드 구역의 수와 같다. 따라서 퍼레이드 구역이 시작되는 왼쪽 변, 끝나는 오른쪽 변으로 나눠 구간마다 갱신해주면 되고, 이것을 이 문제처럼 누적합 배열에서 관리하면 구간 갱신을 단일 값 갱신으로 변형할 수 있다. 달걀의 좌표가 들어오면 그 순간 새그먼트 트리에서 겹치는 퍼레이드 구역을 더해주면 된다.

 

 

 

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

struct Info {
  int y;
  int xs;
  int xe;
  int type; //1: parade_in  2: egg  3: parade_out
};

int solve(){
  int n, m;
  
  cin >> n >> m;
  
  vector<Info> v(n+2*m);
  
  for(int i=0;i<n;i++){
    cin >> v[i].xs >> v[i].y;
    v[i].type= 2;
  }
  for(int i=0;i<m;i++){
    int l, r, b, t;
    
    cin >> l >> r >> b >> t;
    
    v[n+2*i]= {b, l, r, 1};
    v[n+2*i+1]= {t, l, r, 3};
  }
  
  sort(v.begin(), v.end(), [](auto& A, auto& B){
    if(A.y!=B.y)  return A.y<B.y;
    return A.type<B.type;
  });
  
  int treesize= (1<<(((int)ceil(log2(SIZE+1)))+1));
  vector<long> 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 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;
    }
  };
  
  int ans= 0;
  for(Info& elem:v){
    if(elem.type==2){
      ans+= query(query, 0, 100000, 1, 0, elem.xs);
    }else if(elem.type==1){
      update(update, 0, 100000, 1, elem.xs, 1);
      if(elem.xe!=SIZE)  update(update, 0, 100000, 1, elem.xe+1, -1);
    }else{
      update(update, 0, 100000, 1, elem.xs, -1);
      if(elem.xe!=SIZE)  update(update, 0, 100000, 1, elem.xe+1, 1);
    }
  }
  
  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;
}

 

 

 

이건 예전 계정에서 사용한 머지 소트 트리를 이용해 푸는 방식을 조금 변형한 것이다. PST로 푸는 코드는 없다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ALL(v) (v).begin(), (v).end()
#define SIZE 100000

int solve(){
  int n, m;
  
  cin >> n >> m;
  
  vector<pair<int, int>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  int treesize= (1<<(((int)ceil(log2(SIZE+1)))+1));
  vector mstree(treesize, vector<int> ());
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e)  return;
    
    self(self, s, s+(e-s)/2, node*2);
    self(self, s+(e-s)/2+1, e, node*2+1);
    
    mstree[node].resize(mstree[node*2].size()+mstree[node*2+1].size());
    merge(ALL(mstree[node*2]), ALL(mstree[node*2+1]), mstree[node].begin());
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r, int k1, int k2) -> int {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return upper_bound(ALL(mstree[node]), k2)-lower_bound(ALL(mstree[node]), k1);
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r, k1, k2);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r, k1, k2);
      return lsum+rsum;
    }
  };
  
  sort(ALL(v));
  
  for(auto& cord:v){
    mstree[treesize/2+cord.first].push_back(cord.second);
  }
  
  init(init, 0, treesize/2-1, 1);
  
  int ans= 0;
  while(m--){
    int l, r, b, t;
    
    cin >> l >> r >> b >> t;
    
    ans+= query(query, 0, treesize/2-1, 1, l, r, b, t);
  }
  
  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;
}