bluespace   9달 전

N개 숫자가 있을 경우 문제에서는 최대 100,000

세그먼트 트리 메모리는 2N 개 아닌가요??

문제에 min/max 세그먼트 트리를 int d[200000]으로 둘다 잡으니 틀렸다고 하네요..ㅜ

d[300000]으로 하니까 정답이네요.. 왜 그런건가요??

namnamseo   9달 전

세그트리가 접근하는 원소의 수가 웬만하면 2k가 되기 때문에 그렇게 잡는 게 좋습니다.
즉 10만개라면 131072(=217)개의 원소를 사용한다고 생각해버리고, 배열을 262144개를 잡는 거죠.

댓글을 작성하려면 로그인해야 합니다.