처음에는 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대에 결과가 나온 것 같은데

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

너무너무 궁금해요.