HDU 5748 BestCoder Round #84 Bellovin （LIS）（树状数组）

HDU 5748 BestCoder Round #84 Bellovin （LIS）（树状数组）

Bellovin

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 540    Accepted Submission(s): 254

Problem Description

Peter has a sequence a1,a2,...,an and he define a function on the sequence -- F(a1,a2,...,an)=(f1,f2,...,fn), where fi is the length of the longest increasing subsequence ending with ai. Peter would like to find another sequence b1,b2,...,bn in such a manner that F(a1,a2,...,an) equals to F(b1,b2,...,bn). Among all the possible sequences consisting of only positive integers, Peter wants the lexicographically smallest one. The sequence a1,a2,...,an is lexicographically smaller than sequence b1,b2,...,bn, if there is such number i from 1 to n, that ak=bk for 1≤k

Input

There are multiple test cases. The first line of input contains an integerT, indicating the number of test cases. For each test case: The first contains an integer n(1≤n≤100000) -- the length of the sequence. The second line contains n integers a1,a2,...,an(1≤ai≤109).

Output

For each test case, outputn integers b1,b2,...,bn(1≤bi≤109) denoting the lexicographically smallest sequence.

Sample Input

3 1 10 5 5 4 3 2 1 3 1 3 5

Sample Output

1 1 1 1 1 1 1 2 3

Source

​​BestCoder Round #84​​

Recommend

wange2014

题解：求以ai结尾的最长上升子序列（LIS）为多少。

就是求LIS。

AC代码：

//#include#include#include#include#include#define N 1000010using namespace std;int n,a[N];int b[N];int cnt;int s[N];int f[N];int query(int x){ int ret =0; while(x){ ret= max(ret,s[x]); x-= x&-x; } return ret;}void update(int x,int y){ while(x<=cnt) { s[x]=max(s[x],y); x+=x&-x; }}int main(){ int t; scanf("%d",&t); while(t--) { cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[++cnt]=a[i]; } sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-b-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+cnt+1,a[i])-b; } for(int i=1;i<=cnt;i++) s[i]=0; for(int i=1;i<=n;i++) { f[i]=query(a[i]-1)+1; update(a[i],f[i]); printf("%d%c",f[i],i==n?'\n':' '); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。