lyzqm   2년 전

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

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

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

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


onjo0127   2년 전

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

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

lyzqm   2년 전

감사합니다

결국 없는거군요 ㅠㅠ

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