这个题感觉比较简单，但却比较容易想残。。
我不会用树状数组求这个原排列，于是我只好用线段树。。。毕竟 Gromah 果弱马。
我们可以直接依次求出原排列的元素，每次找到最小并且最靠右的那个元素，假设这是第 $i$ 次找的，那么这就是原排列的第 $i$ 项，然后我们就把这个元素删去（变成很大的数），再把这个数以左的数都加 1，进行下一轮。
然后就是裸的最长上升子序列啦~~~
时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100000 + 5
#define M 262144 + 5
#define ls(x) x << 1
#define rs(x) x << 1 | 1 int n, Pos[N], A[N], T[N], F[N]; struct Segment_Tree
{
int Min, delta;
}h[M]; inline void Build(int x, int l, int r)
{
if (l == r)
{
h[x].Min = Pos[l];
return ;
}
int mid = l + r >> ;
Build(ls(x), l, mid);
Build(rs(x), mid + , r);
h[x].Min = min(h[ls(x)].Min, h[rs(x)].Min);
} inline void apply(int x, int d)
{
h[x].Min += d, h[x].delta += d;
} inline void push(int x)
{
if (h[x].delta)
{
apply(ls(x), h[x].delta);
apply(rs(x), h[x].delta);
h[x].delta = ;
}
} inline void Modify(int x, int l, int r, int s, int t, int d)
{
if (l == s && r == t)
{
apply(x, d);
return ;
}
push(x);
int mid = l + r >> ;
if (t <= mid) Modify(ls(x), l, mid, s, t, d);
else if (s > mid) Modify(rs(x), mid + , r, s, t, d);
else Modify(ls(x), l, mid, s, mid, d), Modify(rs(x), mid + , r, mid + , t, d);
h[x].Min = min(h[ls(x)].Min, h[rs(x)].Min);
} inline int Query(int x, int l, int r)
{
if (l == r) return l;
int mid = l + r >> ;
if (h[rs(x)].Min <= h[ls(x)].Min)
return Query(rs(x), mid + , r);
else return Query(ls(x), l, mid);
} int main()
{
#ifndef ONLINE_JUDGE
freopen("3173.in", "r", stdin);
freopen("3173.out", "w", stdout);
#endif scanf("%d", &n);
for (int i = ; i <= n; i ++)
scanf("%d", Pos + i);
Build(, , n);
for (int i = ; i <= n; i ++)
{
int t = Query(, , n);
Modify(, , n, , t, );
Modify(, , n, t, t, n);
if (!T[] || T[T[]] < t)
{
T[++ T[]] = t;
F[t] = T[];
}
else
{
int x = lower_bound(T + , T + T[] + , t) - T;
T[x] = t;
F[t] = x;
}
}
for (int i = , Max = ; i <= n; i ++)
{
Max = Max > F[i] ? Max : F[i];
printf("%d\n", Max);
} #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
3173_Gromah