2가지 방법이 있습니다.
(1) 각각의 Light에 대해서 2차원으로 변형한 후에 누적합으로 구하기.
(2) 2차원 구간에 대한 정보를 Seg Tree에 갱신하면서 구하기.
예를 들어서
1 7
2 3
2 6
3 8
5 6
3 6
이라는 점이 있고
우리가 구해야 하는 것이 x<=a, y<=b 범위에 있는 점의 갯수를 구하기. 라고 해 봅시다. 그러한 경우
일단 1차원을 줄이기 위해서, 정렬을 시킵니다. 2차 정렬 기준으로 y축을 오름차순으로 정렬합시다.
1 7
2 3
2 6
3 6
3 8
5 6
이렇게 한 경우, x<=a이고 y<=b 범위에 있는 점의 갯수를 구한다. 라고 했을 때. a값에 따라서
어느 점까지 seg에 넣을지를 결정할 수 있습니다. 만약에 a = 2라고 해 봅시다. 그러면, x = 3이나 x = 5에 대한 정보를 넣을 필요는 없습니다.
x = 1과 x = 2에 대한 정보만 넣으면 됩니다. 문제 특성상, 그렇게만 해도 충분할 거에요.
dmsrb1002 5년 전
단순 배열을 이용하여 각각의 라이트에 대해 배열을 하나씩 채워넣었더니 시간초과가 나네요.
어떤 알고리즘이 사용되어야 할까요??