想让dalao帮忙瞧瞧思路是否正确：

• 将序列还原成最终的形状

• 每插入一个数之前，用线段树查询这个位置之前的最长上升子序列长度，记为 $k$

• 输出 $k+1$ 然后将 $k+1$ 插入当前位置

• 过样例，但爆零

#include<bits/stdc++.h>
#define M 100001
#define ls p<<1
#define rs p<<1|1
using namespace std;
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
int n,t[M<<2];
struct node
{
	int a,b;
}w[M];
bool cmp(node x,node y)
{
	if(x.a==y.a) return x.b>y.b;
	else return x.a<y.a;
}
bool restore(node x,node y)
{
	return x.b<y.b;
}
void push_up(int p)
{
	t[p]=max(t[ls],t[rs]);
}
int query(int p,int l,int r,int st,int en)
{
	if(st<=l&&r<=en) return t[p];
	int mid=(l+r)>>1,MAX=0;
	if(st<=mid)  MAX=max(MAX,query(ls,l,mid,st,en));
	if(en>mid) MAX=max(MAX,query(rs,mid+1,r,st,en));
	return MAX;
}
void update(int p,int l,int r,int x,int k)
{
	if(l==r)
	{
		t[p]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,k);
	else update(rs,mid+1,r,x,k);
	push_up(p);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) w[i].a=read(),w[i].b=i;
	sort(w+1,w+n+1,cmp);
	for(int i=1;i<=n;i++) w[i].a=i;
	sort(w+1,w+n+1,restore);
	for(int i=1;i<=n;i++)
	{
		int j=w[i].a;
		int k=query(1,1,n,1,j)+1;
		printf("%d\n",k);
		update(1,1,n,j,k);
	}
	return 0;
}