7469번 - K번째 수
쿼리를 오프라인으로 처리해서 각 쿼리마다 Insert, Remove 시행하는데 O(1)이면 O(sqrt(N) *(N+Q))로 충분히 시간내에 풀 수있을것 같은데
어떠한 자료구조를 이용해야 Insert, Remove가 상수복잡도로 나올지 모르겠습니다.
저는 세그먼트트리로 O(logN)로 위의 작업이 시행되서 시간이 초과되는것 같습니다.
시간을 줄일 수 있는 방법이 있을까요?
Mo's algorithm으로 풀기에는 무리가 있는 것 같습니다. O(1)에 저 연산을 구현하는 것은 조금 힘들어 보이네요..
Merge Sort Tree나 Persistent Segment Tree를 공부하시면 온라인 알고리즘으로 문제를 풀 수 있습니당
감사합니다
결국 없는거군요 ㅠㅠ
같은 방법으로 풀어서 964ms로 정답을 받았습니다.
Insert Remove 를 매번 log N만큼 돌면서 업데이트하지 않고
각 쿼리(m)마다 값이 변하는 친구들을 먼저 쫙 구해놓은 다음에 한방에 업데이트하면 좀 더 빨라집니다.
댓글을 작성하려면 로그인해야 합니다.
lyzqm 6년 전
쿼리를 오프라인으로 처리해서 각 쿼리마다 Insert, Remove 시행하는데 O(1)이면 O(sqrt(N) *(N+Q))로 충분히 시간내에 풀 수있을것 같은데
어떠한 자료구조를 이용해야 Insert, Remove가 상수복잡도로 나올지 모르겠습니다.
저는 세그먼트트리로 O(logN)로 위의 작업이 시행되서 시간이 초과되는것 같습니다.
시간을 줄일 수 있는 방법이 있을까요?