hdu 5748 Bellovin【最长上升子序列】

题目大意：

解题思路：
题目要求为：输出与已知序列的每一个元素的f(i)(f(i)的定义如题)相同的字典序最小的序列。稍微思考便知，其实就是叫我们求出原序列的f(i)，这个很容易做到，只要在最长上升子序列的模板题上稍微做一些改动，记录下原序列每一个元素的f(i)即可。具体实现见代码。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5+;

int rise[N],ans[N];

int n;
int main(){

    int T;scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        int len=;rise[]=-;

        for(int i=;i<=n;i++){

            int data;scanf("%d",&data);

            if(data>rise[len])rise[++len]=data,ans[i]=len;     //记录以i为末尾的最长上升子序列的长度

            else {

                int loc=lower_bound(rise+,rise++len,data)-rise;     //最长上升子序列用lower_bound

                rise[loc]=data;

                ans[i]=loc;     //记录以i为末尾的最长上升子序列的长度

            }

        }

        for(int i=;i<=n;i++)

            i==n?printf("%d\n",ans[i]):printf("%d ",ans[i]);

    }

}