Bellovin
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 858 Accepted Submission(s): 395
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<i and ai<bi.
Input
There are multiple test cases. The first line of input contains an integer T, 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, output n 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
Source
题意：给一个序列,求出每个位置结尾的最长上升子序列;然后找一个字典序最小的这个函数值相同的子序列;
其实就是求每个位置结尾的最长上升子序列的长度组成的序列。
题解:固定尾部的最长上升子序列的长度nlgn处理
exm[j] 表示长度为j的的序列的最后一个值的大小
1 /******************************
2 code by drizzle
3 blog: www.cnblogs.com/hsd-/
4 ^ ^ ^ ^
5 O O
6 ******************************/
7 //#include<bits/stdc++.h>
8 #include<iostream>
9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<cmath>
14 #define ll __int64
15 #define PI acos(-1.0)
16 #define mod 1000000007
17 using namespace std;
18 int t;
19 int a[100005];
20 int ans[100005];
21 int n;
22 int main()
23 {
24 scanf("%d",&t);
25 {
26 for(int i=1; i<=t; i++)
27 {
28 scanf("%d",&n);
29 scanf("%d",&a[0]);
30 ans[0]=1;
31 int exm[100005];
32 int top=1;
33 exm[1]=a[0];
34 for(int j=1; j<n; j++)
35 {
36 scanf("%d",&a[j]);
37
38 if(a[j]>exm[top])
39 {
40 top=top+1;
41 exm[top]=a[j];
42 ans[j]=top;
43 }
44 else
45 {
46 int pos=lower_bound(exm,exm+top,a[j])-exm;
47 exm[pos]=a[j];
48 ans[j]=pos;
49 }
50 }
51 for(int j=0; j<n; j++)
52 {
53 if(j==0)
54 printf("%d",ans[j]);
55 else
56 printf(" %d",ans[j]);
57 }
58 printf("\n");
59 }
60 }
61 return 0;
62 }
HDU 5784 最长上升子序列的长度nlgn(固定尾部)
原文：http://www.cnblogs.com/hsd-/p/5719961.html
