Written with StackEdit.
Description
给定一个序列,初始为空。现在我们将(1)到(N)的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?
Input
第一行一个整数(N),表示我们要将(1)到(N)插入序列中,接下是(N)个数字,第(k)个数字(X_k),表示我们将(k)插入到位置(X_k(0leq X_kleq k-1,1leq kleq N)),
Output
(N)行,第(i)行表示(i)插入(X_i)位置后序列的最长上升子序列的长度是多少。
Sample Input
3
0 0 2
Sample Output
1
1
2
HINT
(100\%)的数据 (nleq100000).
Solution
- 如果我们已经得到了最后的序列,我们可以用(O(nlogn))的算法计算出(LIS),同时维护(ans[i]),表示以(i)作为结尾的上升子序列的最大长度.
- 再令(g[i])表示最终要输出的答案,即插入(i)后的(LIS)长度.
- 因为整个序列是从小到大插入的,所以(g[i]=max_{j=1}^{i}ans[j].)
- 使用前缀和优化一下即可.
- 维护元素的插入可以写一颗平衡树.
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int MAXN=1e5+10;
int a[MAXN],qlen=0;
int n;
struct FhqTreap
{
int x,y;
struct node
{
int lson,rson,siz,weight,key;
} treap[MAXN];
int idx,root;
FhqTreap()
{
x=0,y=0;
idx=0;
root=0;
treap[0].key=0;
treap[0].lson=treap[0].rson=0;
treap[0].weight=0;
treap[0].siz=0;
}
#define rt treap[o]
#define ls treap[treap[o].lson]
#define rs treap[treap[o].rson]
inline int newnode(int key)
{
int o=++idx;
rt.lson=rt.rson=0;
rt.siz=1;
rt.weight=rand();
rt.key=key;
return o;
}
inline void pushup(int o)
{
rt.siz=ls.siz+rs.siz+1;
}
int merge(int x,int y)
{
if(!x || !y)
return x+y;
if(treap[x].weight<treap[y].weight)
{
treap[x].rson=merge(treap[x].rson,y);
pushup(x);
return x;
}
else
{
treap[y].lson=merge(x,treap[y].lson);
pushup(y);
return y;
}
}
void split(int &x,int &y,int k,int o)
{
if(!o)
x=y=0;
else
{
if(k<=ls.siz)
{
y=o;
split(x,rt.lson,k,rt.lson);
}
else
{
x=o;
split(rt.rson,y,k-ls.siz-1,rt.rson);
}
pushup(o);
}
}
void ins(int key,int pos)
{
split(x,y,pos,root);
y=merge(newnode(key),y);
root=merge(x,y);
}
void dfs(int o)
{
if(!o)
return;
dfs(rt.lson);
a[++qlen]=rt.key;
dfs(rt.rson);
}
void getseq()
{
dfs(root);
}
}T;
#define inf 0x7fffffff
int f[MAXN],ans[MAXN];
int main()
{
srand(19260817);
n=read();
for(int i=1;i<=n;++i)
{
int pos=read();
T.ins(i,pos);
}
T.getseq();
memset(f,0x7f,sizeof f);
f[0]=-inf;
for(int i=1;i<=n;++i)
{
int t=upper_bound(f,f+n+1,a[i])-f;
f[t]=a[i];
ans[a[i]]=t;
}
for(int i=1;i<=n;++i)
printf("%d
",ans[i]=max(ans[i-1],ans[i]));
puts("");
return 0;
}