(17131) 여우가 정보섬에 올라온 이유

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

단계별로 풀어보기

49단계(스위핑) 4번째

 

 

 

북서풍 문제와 마찬가지로 스위핑과 새그먼트 트리를 결합하여 푸는 문제.

어떤 별을 기준으로 잡고 그 별이 가운데 아래 별이 되는 V자형 별자리의 개수는, 그 별의 왼쪽 위 별의 개수와 오른쪽 위 별의 개수의 곱과 같다. 따라서 y좌표 기준으로 내림차순, 같다면 x좌표 기준 오름차순으로 모든 별을 탐색한다. 새그먼트 트리를 이용해 구간합을 구하면 된다. 주의할 점은 y좌표가 같은 별은 세면 안 되므로 업데이트를 별을 탐색할 때마다 하지 않고 y좌표가 달라지는 별을 탐색할 때 이전 별들을 일괄 업데이트해줘야 한다.

 

원래 y좌표가 같은 왼쪽 별을 cnt로 관리하고 왼쪽 위 별 개수를 구한 뒤 cnt를 빼주는 방법을 이용했는데 계속 틀렸다고 해서 일괄 업데이트 방식으로 수정했더니 맞았다. LLM으로도 제대로 답을 못 찾는데 왜 틀리는지 의문이다. 너무 많이 제출해서 스크린샷은 맨 위만 잘랐다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define SIZE 400001
#define p 1000000007

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  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;
    v[i].first+= 1+SIZE/2;
  }
  
  int treesize= (1<<(((int)ceil(log2(SIZE+1)))+1));
  vector<long> segtree(treesize);
  
  sort(v.begin(), v.end(), [](auto& A, auto& B){
    if(A.second!=B.second)  return A.second>B.second;
    return A.first<B.first;
  });
  
  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;
    }
  };
  
  int y= -200001;
  vector<int> buffer;
  for(auto& star:v){
    if(y!=star.second){
      for(int x:buffer)  update(update, 1, SIZE, 1, x);
      
      buffer.clear();
      y= star.second;
    }
    
    long lstar= query(query, 1, SIZE, 1, 1, star.first-1);
    long rstar= query(query, 1, SIZE, 1, star.first+1, SIZE);
    
    ans= (ans+lstar*rstar)%p;
    
    buffer.push_back(star.first);
  }
  
  cout << ans;
  
  return 0;
}