devbelly   3년 전

[문제요약] 쿼리가 주어집니다. 1번 쿼리는 구간 (l,r)이 오름차순인지 알아내는 것이고, 2번 쿼리는 l과 r의 값을 바꾸는 것입니다.

[코드] http://boj.kr/2619d0fb02a94fbdb45b8aed0e10e7cd

접근 방법은 세그먼트 트리 노드에 pair값을 사용해 자신이 관리하는 구간이 오름차순이라면 pair의 first와 second를 기록하고, 오름차순이 아니라면

0 0 을 넣어 풀려고 시도했습니다. 리프노드에는 first와 second 값을 동일하게 해놨습니다.

query가 되게 누더기처럼 작성되어서 아마 query안에서 틀린 것 같은데 반례를 잘 모르겠습니다....

prarie   3년 전

결론적으로 말하면 query 부분에서 합쳐주는 부분에서 반례가 발생하네요

query 부분 고친 정답 소스

https://www.acmicpc.net/source...


비재귀 세그먼트 트리를 짤 때는 연속적인 부분을 처리할 경우 조심히 짜야 합니다

반례는 랜덤으로 찍은거라 잘 모르겠네요

재귀로 하면 연속적인 부분을 그렇게 고려하지 않아도 되기 때문에 짜기가 편합니다

https://www.acmicpc.net/source...


그리고 다른 풀이로는 a[i] <= a[i + 1] 인 경우 p[i] = 0, 아니면 p[i] = 1 로 두고 [l, r) 까지 합을 구해서 합이 0 인지 아닌지 체크하는 방법으로도 풀 수 있습니다.  (펜윅트리)

devbelly   3년 전

선생님 감사합니다......ㅠㅠㅠ

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