Coordinate-Compression1 [3] 좌표 압축 (Coordinate-Compression) 좌표 압축은 PS에서 정말 많이 쓰이는 테크닉으로, 세그트리 같이 구간 쿼리를 해결하기 위해 많이 사용한다. 세그트리는 주어진 범위의 모든 영역을 Leaf node로 사용하기 때문에, 해당 범위가 커지면 좌표 압축이 필요하다. 결국 좌표 압축은, 해당 좌표를 0,1,2 ~ 의 값으로 치환하는 것인데, 그 자체는 매우 어렵고 이해가 되지 않는 개념은 아니다. for (int i = 0; i > comp[i]; v.push_back(comp[i]); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for (int i = 0; i < n; i++) { comp[i] = lower_bound.. 2020. 9. 28. 이전 1 다음
