plumberry   2년 전

처음에는 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   2년 전

4번 쿼리만 M개 들어오면

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

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


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

ntopia   2년 전

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

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

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

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

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

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

cubelover   2년 전

4번 쿼리가 많이 들어올 수 있기 때문에, 모든 쿼리의 시간복잡도를 O(k2 log n) 정도로 줄여야 할 것 같습니다.

저는 각 노드가 자신의 구간에 대한 4번 쿼리의 답을 계속 들고 있는 방법으로 풀었습니다. 예를 들어 [2, 4]를 덮는 노드라면 a[2] 1k + a[3] 2k + a[4] 3k를 0 이상 10 이하의 k에 대해 들고 있습니다.

두 노드를 합치는 과정을 이항정리를 사용해서 O(k2)에 행할 수가 있기 때문에, Rotate 연산을 할 때마다 노드의 값을 새로 갱신해 주면 [l, r]을 한 노드에 모아준 뒤 값을 출력해주면 O(k2 log n)의 시간에 모든 쿼리를 처리할 수가 있습니다.

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