(16357) Circuits

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

단계별로 풀어보기

52단계(세그먼트 트리 2) 7번째

 

 

 

갑자기 난이도가 상당히 뛴 응용 문제다. 우선 회로의 X좌표는 수평선에 아무런 영향이 없으므로 Y좌표 구간만 가진 1차원 문제라고 생각해도 된다. 만약 수평선이 하나라면 입력받는 회로의 Y좌표 구간마다 1을 더한 뒤 최대값 세그먼트 트리로 전체 구간의 최대값을 구하면 된다. 문제는 수평선이 두 개라는 것으로 수평선이 겹치는 회로는 중복으로 카운팅하면 안 된다. 따라서 하나의 회로를 고정한 뒤 겹치는 회로는 구간에서 값을 1 빼는 업데이트 후 최대값을 구하면 된다. 만약 고정하는 회로를 항상 아래쪽 회로로 한다면 그 아래 회로는 겹치지 않더라도 이미 탐색이 끝났으므로 다시 구간에 값을 추가하는 업데이트를 하지 않아도 된다.

따라서 모든 회로를 시작 y좌표 기준으로 정렬한 뒤 스위핑으로 수평선을 올려가며 그 위쪽 구간에서만 최대값을 구하면 아래쪽 수평선이 고정되었을 때 최대값을 구할 수 있고 이를 모든 구간에 반복하면 된다.

 

 

 

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

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