LIS

• 우선 A[0]으로 시작하는 부분배열들(=prefix들)의 LIS의 길이의 합을 구하는 것만 생각해보자
• 모든 i에 대해서 A[i]로 끝나는 LIS의 길이를 미리 구해둔다면, A[..i]의 LIS의 길이는 max({A[..i-1]의 LIS의 길이}, {A[i]로 끝나는 LIS의 길이}) 로 O(1)에 구할수 있고, 모든 prefix들의 LIS의 길이는 O(n)에 구할수 있다.
• 모든 i에 대해 A[i]로 끝나는 LIS의 길이를 구하는 것은 O(nlogn)이므로, 총 시간복잡도는 O(nlogn)
• 이제 이것을 다시 A[0:], A[1:], A[2:], … 에 대해서 모두 구해주면 된다. 그러면 전체 시간복잡도는 O(n^2logn)

"""Solution code for "BOJ 9702. LIS".

- Problem link: https://www.acmicpc.net/problem/9702
- Solution link: http://www.teferi.net/ps/problems/boj/9702

Tags: [lis]
"""

import collections
import sys
from teflib import psutils
from teflib import seqtask


@psutils.gcj_style
def main():
    N = int(sys.stdin.readline())
    s = collections.deque(int(sys.stdin.readline()) for _ in range(N))

    answer = 0
    for _ in range(N):
        length = 0
        for l in seqtask.longest_inc_subseq_lengths_by_last_elem(s):
            if l > length:
                length = l
            answer += length
        s.popleft()

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq_lengths_by_last_elem