Problem Description A numeric sequence of ai is ordered if
a1
. Let the subsequence of the given numeric sequence (
a1,a2,…,aN
) be any sequence (
ai1,ai2,…,aiK
), where
1≤i1
. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.
S[ i , j ] indicates (
ai,ai+1,ai+2,…,aj
) .
Your program, when given the numeric sequence (
a1,a2,…,aN
), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of (
a1,a2,…,aN
).
Input Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbers
a1,a2,…,aN
separated by exact one space.
Process to the end of file.
[Technical Specification]
1≤n≤100000
0≤ai≤1000000000
Output For each case，.output the answer in a single line.
Sample Input
3
1 2 3
2
2 1
Sample Output
1
3
Source BestCoder Round #21
这道题真心不会，看了题解和别人博客，问了bin巨，搞了半天才理解。
树状数组优化的是求解LIS和LIS最大的时候最靠右的位置。
#include
#include
#include
#include
#include
#include
#include
#include
#include