temp   10달 전

다른분들의 소스를 봐도 도무지 이해가 되지 않습니다.

기본적인 개념은 알겠는데 어떻게 활용해서 이 문제에 적용시키는지 이해가 되지 않습니다 ㅠㅠ

혹시 팁을 주실수있을까요?

noeffserv   10달 전

어디까지 알고 계신지는 모르겠지만..

펜윅트리를 업데이트 할때, L 에서 1을 증가시키게 되면,

L, L+1, L+2 ... 에 모두 영향을 미치잖아요. 

그런데 문제를 풀기 위해서는 R 부근 까지만 영향을 끼치는게 바람직하죠. 

그래서 R 에선 -1을 증가시켜버립니다.

그렇게 되면 L 부터 R 부근까지는 1을 증가시킨 효과가 발휘되고

R 부근 이후는 1을 증가시킨효과가 -1로 인해 상쇄 돼버립니다.

결국 L ~ R 까지 식물이 존재한다는 것을 펜윅트리로 알수 있게 됩니다.

여기다가 식물이 하나씩 추가 될때마다 펜윅트리에 위 방식처럼 업데이트 해줍니다.

그렇게 되면 어떤 x 좌표에 식물이 몇개나 겹쳐져 있는지 알 수 있습니다.

noeffserv   10달 전

L - R    ->    L부터 R부근 까지

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