[原创]华中农业大学第五届程序设计大赛 G Sequence Number [树上二分]【数据结构】
[原创]华中农业大学第五届程序设计大赛 G Sequence Number [树上二分]【数据结构】
2017-05-26 21:50:28 Tabris_ 阅读数:401
博客爬取于2020-06-14 22:40:32
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773915
题目链接:http://acm.hzau.edu.cn/problem.php?id=1205
————————————————————————————————————————————
1205: Sequence Number
Time Limit: 1 Sec Memory Limit: 1280 MB
Submit: 934 Solved: 242
[Submit][Status][Web Board]
Description
In Linear algebra, we have learned the definition of inversion number:
Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each other. If exist positive integers i , j, ( 1 ≤ i < j ≤ n and A[i] > A[j]), < A[i], A[j]> is regarded as one of A’s inversions. The number of inversions is regarded as inversion number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>, <6,1>,and the inversion number is 5.
Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1 ≤ i ≤ j ≤ n and A[i] <= A[j], < A[i], A[j]> is regarded as one of A’s sequence pair. The number of sequence pairs is regarded as sequence number. Define j – i as the length of the sequence pair.
Now, we wonder that the largest length S of all sequence pairs for a given array A.
Input
There are multiply test cases.
In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array, the 2th ~n+1th line are one number per line, indicates the element Ai (1<=Ai<=10^9) of the array.
Output
Output the answer S in one line for each case.
Sample Input
5
2 3 8 6 1
Sample Output
3
——————————————————————————————————————
题目大意:
就是给你一个序列,然你求下的最大值
解题思路:
首先记录每个数的索引,
然后按数值大小升序排序
然后遍历每次将索引更新到树上,并查找索引在他之前最小的那个位置是多少.
维护最大值就好了
复杂度
听说用单调栈降到
附本题代码
————————————————————————————————
1 | # include <bits/stdc++.h> |