업데이트 : (x, y) 에 점 추가
쿼리 : 특정 직사각형 안에 있는 점 세기
이걸 온라인으로 섞어가면서 하는거 가능함? 범위는 다 10만
Egg가 딱 이건데 에그는 업데이트 몰아서 주고 쿼리하는거라 PST나 MST로도 처리되는데 업데이트랑 쿼리가 섞여서 나오면 어떻게 함?
동적 2차원 세그만들면 공간복잡도 O(Nlg^2N)에 될 것 같기도 한데 이거 맞나? 너무 복잡해보이는데
어떤 독스 읽으니까 되긴 되는데 값 변경이 안 된다고 하기도 하던데.. 이건 왜 안 되는건지도 모르겠네
일단 2차원 다이나믹세그로 로그제곱에 됨 (IOI 13 Games)
동적세그에 BBST박으면 쿼리 로그제곱 공간 로그상수에 가능함
왜,, 이걸 여태 몰라서,, ㄱㅅㄱㅅ
BBST면 set같은거 아닌가? 세그에 set을 박으면 메모리가 줌?
BBST는 메모리가 O(N)이니깐? 세그 각 노드에 BBST 관리하면 한개 원소가 총 logX번 들어가서 공간 NlogX임
그건 좀 더 공부해봐야겠네,, 일단 2차원동적세그부터 공부해야겠다 ㄱㅅㄱㅅ
동적세그에 셋박는게 더 쉽긴함 1차원세그만 공부하면 돼서... IOI13 Games는 커팅해야하는데 커팅법은 전명우님 블로그가 근본
아 이해했다 무슨 느낌인지 알겠음 걍 세그 대신 셋 박고 셋에서 작업하는거구나
무서 워요
Treap같은 BBST구조로 잘 될것 같은데 몬가 잘 안되네… 다이나믹 세그 없이도 될듯말듯 한데 흠
fractional cascading으로 시간 메모리 둘 다 로그에 되는 걸로 앎