fbfbf1   3년 전

예제는 맞게 뜨고 게시판에 있는 반례도 다 맞게 뜨는 것 같은데

한 4%정도 갔다가 틀렸다고 나오네요

update할 때랑 곱할 때랑 초기화 할 때랑 다 모듈러 연산까지 해줬는데

걸리는게 있다면 66~69번째 줄인데

여기서 잘못 된 걸까요

0으로 update를 하고 난 뒤에

0이 아닌 수로 update를 하게 되서

그냥 곱하기만 하면 0이 나와서

그냥 다시 초기화를 해줬습니다.

djm03178   3년 전

38번째 줄이 문제입니다.

이미 모듈러가 된 수를 다시 나누기를 통해 필요한 값을 얻어낼 수 없습니다. 게다가 long double과 같은 실수형을 사용하면 값의 계산 결과에도 오차가 발생합니다. 실수형은 답의 출력에 오차가 허용되는 문제가 아닌 한은 절대 사용하지 않는 것이 좋습니다.

세그먼트 트리의 업데이트는 기본적으로 리프를 먼저 업데이트하고, 업데이트된 정보들을 이용하여 부모 노드를 업데이트하는 방향으로 가는 것이 좋습니다. 부모를 먼저 업데이트해도 되는 경우는 자식의 결과를 몰라도 항상 답을 알 수 있는 경우인데 이 문제는 그렇지 않습니다. 코드 전체의 일관성을 생각해도 init에서 하는 것과 순서가 반대가 된 상황입니다.

fbfbf1   3년 전

@djm03178 답변 정말 감사드립니다!

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