plumberry   3년 전

처음에는 list, vector, 배열로 했다가 시간 초과가 나서,

여차저차 검색해보다가 cubelover님이 올리신

splay tree 글을 보고, splay tree 로 구현했으나

여전히 시간 초과가 납니다.


삽입, 삭제, 변경은 O(logn)에 처리되도록 구현했고

4번 op는 O(n)에 처리하도록 구현했는데도 시간 초과가 나오네요.

(splay 과정에서 index^k 값을 곱할 수 없다고 판단해서 find(l) 한 뒤,

오른쪽 서브 트리를 inorder로 순회하며 값을 계산하였습니다.)


나름대로 시간을 줄여보고자, 4번 OP의 index^k를

미리 계산해서 캐싱해두고 배열에서 참조하는 방식과,


매번 삽입 할 때마다 node를 생성하는 시간도 줄이려고

미리 생성해두고 사용했음에도 불구하고 시간 초과가 나왔습니다..


문제를 푼 분이 3분이고, 대부분 1초대에 정답이 나오고,

cubelover님 같은 경우에는 300ms대에 결과가 나온 것 같은데

어떻게 풀었는지 궁금합니다...

너무너무 궁금해요.

ntopia   3년 전

4번 쿼리만 M개 들어오면

전체 시간복잡도가 O(NM) 이라 TLE 나겠네요.

최적화를 열심히 해도 기본 연산량 (=시간복잡도) 자체를 줄이지 않으면 계속 TLE 날거에요.


조심스럽게 얘기해보자면 실력에 비해 너무 어려운 문제가 아닐까... 싶습니다.

ntopia   3년 전

저도 정확한 풀이는 모르지만 입코딩을 한 번 해보자면

트리 리프마다 a[i] 가 담겨있는게 아니라

a[i] * (x+i)^k  가 담겨있다고 생각을 하면

[l, r] 쿼리가 들어왔을 때 구간의 합을 구하면 다항식이 나올테고, 거기에 적절한 x를 대입하면 원하는 값이 나오겠죠.

이걸 이용하는게 아닐까 싶습니다.

입코딩을 열심히 했으니 저도 한 번 짜보러 가야겠네요...

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