시장 선거 포스터
Problem
https://www.acmicpc.net/problem/2370
Idea
poster 너비를 구간트리로 표현해 poster를 붙일 시마다 이전 poster가 붙어있는지 쉽게 판단 가능하다.
업데이트 구간이 커 lazy처리가 필요하고, 너비가 10^8 이기에 좌표 압축이 필요하다.
좌표 압축
- 절대 너비구간이 상대적으로 몇번째로 (최대 N) 큰지 표현(중복제거)
1 40
2 60
8 100
30 40
80 100
order: 1 2 8 30 40 40 60 80 100 100
compressed:1 2 3 4 5 6 7 8
ordered = new int[N * 2];
compressed = new ArrayList<Integer>();
int cnt = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
map[i] = new Poster(l, r);
ordered[cnt++] = l;
ordered[cnt++] = r;
}
Arrays.sort(ordered);
int s = 0;
cnt = 0;
for (int i = 0; i < 2 * N; i++) {
if (s != tmp[i]) {
compressed.add(tmp[i]);
s = tmp[i];
}
}
Related
https://www.acmicpc.net/problem/13167