https://www.acmicpc.net/problem/12899
- 2월동안 187문제 풀기(지난달 누적 87개) (65/187)
- 펜윅 트리 써서 위치를 마킹해두는 유형의 문제.
- 나는 누적값이 바뀌는 위치를 바이너리 서치로 찾아서 $O(\log^2{N})$ 만큼 쿼리당 처리 시간이 든다.
- 쿼리당 처리 시간을 줄이려면 펜윅 트리를 확실하게 이해해야 하는것 같다. 쌓아가면서 절반씩 나눈 값을 조회하면 된다.
1
2
3
4
5
6
7int ans = 0; for(int e = (1<<20); e > 0; e /= 2) { if (tree[ans] < target) { target -= tree[ans]; ans += e; } }
1 |
|