G1 5676 음주코딩

30분 23초
세그먼트 트리 문제인 것이 한눈에 보인다.
곱했을 때 양수, 음수, 0으로만 구별하므로 양수면 1, 음수면 -1로 바꿔서 저장한다.

P5 11003 최솟값 찾기

1시간 14분 9초
슬라이딩 윈도우를 생각했다가 어떻게 구현할지 생각을 못해내서 세그먼트 트리로 풀었다.
알고보니 deque를 사용하여 새로운 $A_i$를 deque에 넣을 때 뒤에서부터 $A_i$보다 큰 값은 삭제한다. 이렇게 하면 deque 내부는 정렬이 된다.