HDU 5748 Bellovin

Problem Description

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

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

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

1

1 1 1 1 1

1 2 3

稍微想想大概就能发现了，答案其实就是那一堆的fi，所以剩下就是如何来快速求最长上升子串的问题了。

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int N = 4e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x7FFFFFFF;
int T, n, a[N], b[N], f[N], g[N];

int get(int x)
{
    int res = 0;
    for (int i = x; i; i -= low(i)) res = max(f[i], res);
    return res;
}

void insert(int x, int y)
{
    for (int i = x; i <= n; i += low(i)) f[i] = max(f[i], y);

}


int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        rep(i, 1, n) scanf("%d", &a[i]), b[i] = a[i], f[i] = 0;
        sort(b + 1, b + n + 1);
        rep(i, 1, n)
        {
            int x = lower_bound(b + 1, b + n + 1, a[i]) - b;
            g[i] = get(x - 1) + 1, insert(x, g[i]);
        }
        rep(i, 1, n) printf("%d%s", g[i], i == n ? "\n" : " ");
    }
    return 0;
}