sample output은 만족하는데 문제가 뭘까요? 이 알고리즘으로는 시간이 오래 걸리나요? 근데 이 알고리즘말고는 떠오르는게 없어요 힌트라도 좀 주세유ㅠㅠㅠ

http://en.m.wikipedia.org/wiki/Segment_tree 를 참고하시기 바랍니다. 꽤 복잡한 내용이라서... 이해하기 좀 시간이 걸리실거에요.