How can we find the Longest Bitonic Sequence using a Segtree?

Правка en2, от Anthony_Smith, 2021-12-31 06:13:39

The problem of finding the Longest Bitonic Sequence (the longest sequence that either first decreases then increases, or first increases then decreases) is well known. We can just do DP, keep for each prefix the longest increasing and decreasing subsequence and also for each suffix. Then just loop through all possible "middle" indices (indices where the sequence transitions from increasing to decreasing or the other way around) and test in that way. The complexity would be O(NlogN + N) (NlogN for each DP, test N center indices) I think.

But I was wondering, whaf is we are given queries that ask for the LBS in a subarray? As far as I know, this has not been in any contest I can find online. I thought we could use a Segment Tree to do this, but I don't know what we'd need to maintain in the nodes. I think we would need to maintain the LIS and LDS (longest increasing/decreasing subsequences) ending at each index as well as the longest bitonic subsequence ending at each index. But this would make queries O(N), which I don't think is good enough. Is there another way to do this?

Теги problem solving

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Anthony_Smith 2021-12-31 07:48:58 251
en2 Английский Anthony_Smith 2021-12-31 06:13:39 185
en1 Английский Anthony_Smith 2021-12-31 06:11:45 979 Initial revision (published)