A question about Longest Non-decreasing Sequence

Revision en1, by rlajkalspowq, 2019-10-04 08:55:21

I'm recently thinking of a problem. Given a sequence $$$a$$$, find the value of $$$\sum_{l=1}^n \sum_{r=l+1}^n lis(a[l...r])$$$. Where $$$lis(a)=$$$ the longest non-decreasing sequence of $$$a$$$ and $$$n$$$ is the length of $$$a$$$. $$$n$$$ is large to $$$10^5$$$ and $$$a_i$$$ is extremely small, only $$$20$$$? I can't think of a solution. Can anyone help me? Please.

Tags lis

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rlajkalspowq 2019-10-04 08:55:21 378 Initial revision (published)