[일반] 쉬운 문제 질문

[익명(119.70)]

백준 2357번 세그먼트 트리로 최대 최소 구하기인데

이거 트리 2개 구현하기 귀찮아서 pair를 노드로 하는 트리 하나로 짰더니 시간초과 나는데 원래 분리해야되나요?

http://boj.kr/a2efeceb28ba4d2e92a48ec8174faf66

[익명(61.255)]

난 그냥 합쳐서 풀었는데

[시아닌(kimjg1119)]

세그 하나는 부호 바꿔 넣어서 관리하면 되는것을 어찌하여...

[익명(119.70)]

어허....그런방법이

[즈우북(121.161)]

호출을 두번씩 하니까 그렇지 temp.first = min(query(start,end,node*2,nleft,mid).first, query(start,end,node*2+1,mid+1,nright).first); temp.second = max(query(start,end,node*2,nleft,mid).second, query(start,end,node*2+1,mid+1,nright).second); 이런거 query 한 번 호출에 절반 사이즈 4번 호출하는게 돼서 시간복잡도 올라가잖아. 한 번 호출한거 저장해놓고 그거 가져다 쓰게 해야지.