DP (Large)

• A[i]를 포함하는 LIS의 길이를 구하라는 문제.
• 이것은 A[i]로 끝나는 LIS와 A[i]로 시작하는 LIS를 합쳐놓은 것이 된다.
• 모든 i에 대해서 A[i]로 끝나는 LIS와 A[i]로 시작하는 LIS를 O(nlogn)에 구해두면, 각 쿼리를 O(1)에 처리할수 있다
• 총 시간복잡도는 O(nlogn + q)

"""Solution code for "BOJ 31503. DP (Large)".

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

Tags: [lis]
"""

import sys
from teflib import seqtask


def main():
    _N, Q = [int(x) for x in sys.stdin.readline().split()]
    D = [int(x) for x in sys.stdin.readline().split()]

    len_by_last = seqtask.longest_inc_subseq_length_by_last_elem(D)
    len_by_first = seqtask.longest_inc_subseq_length_by_first_elem(D)

    for _ in range(Q):
        A = int(sys.stdin.readline()) - 1
        print(len_by_last[A] + len_by_first[A] - 1)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.seqtask.longest_inc_subseq_length_by_last_elem
  • teflib.seqtask.longest_inc_subseq_length_by_first_elem