https://www.acmicpc.net/problem/25566
접근법 - 실패, 시간초과
- index tree를 3번 사용하는데 시간초과..
- map을 써서 좌표압축을 해서 그런가 ==> map을 써서 시간초과 나는듯
접근법
- 뭔데 이렇게 해맸을까
- 좌표 압축(map안쓰고)
- r로 정렬 => r보다 작은 것들을 대상으로
- l 과 r 사이의 합 => l로 업데이트가 되었을 것이므로 l ~ r 사이의 효과
- l로 update
접근법 - 공식해설
- https://icpc-sinchon.io/suapc
- 세그먼트트리 사용하지 않으므로 좌표 압축도 필요 없음
- l로 정렬하고(r은 역순) 하나씩 탐색
- 현재의 r보다 기존의 r이 크면 그 곳에 포함 (기존 것이 왼쪽, 오른쪽 모두 포함하니까)
- 현재의 r이 커지면 새로운 것으로 생각(기존 것이 왼쪽은 커도, 오른쪽은 포함 못함)
newbieski