lyzqm   6년 전

쿼리를 오프라인으로 처리해서 각 쿼리마다 Insert, Remove 시행하는데 O(1)이면 O(sqrt(N) *(N+Q))로 충분히 시간내에 풀 수있을것 같은데

어떠한 자료구조를 이용해야 Insert, Remove가 상수복잡도로 나올지 모르겠습니다.

저는 세그먼트트리로 O(logN)로 위의 작업이 시행되서 시간이 초과되는것 같습니다.

시간을 줄일 수 있는 방법이 있을까요?


onjo0127   6년 전

Mo's algorithm으로 풀기에는 무리가 있는 것 같습니다. O(1)에 저 연산을 구현하는 것은 조금 힘들어 보이네요..

Merge Sort Tree나 Persistent Segment Tree를 공부하시면 온라인 알고리즘으로 문제를 풀 수 있습니당

lyzqm   6년 전

감사합니다

결국 없는거군요 ㅠㅠ

pichulia   3년 전

같은 방법으로 풀어서 964ms로 정답을 받았습니다.

Insert Remove 를 매번 log N만큼 돌면서 업데이트하지 않고 

각 쿼리(m)마다 값이 변하는 친구들을 먼저 쫙 구해놓은 다음에 한방에 업데이트하면 좀 더 빨라집니다.

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