#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

int tot=0;
int dp[maxn],a[maxn];

struct rnode
{
	int l,r;
	int v;
	rnode()
	{
		l=0;
		r=0;
	}
}tre[maxn];

void push_up(int k)
{
	tre[k].v=max(tre[tre[k].l].v,tre[tre[k].r].v);
}

void update(int k,int l,int r,int x,int v)
{
	if(l==r)
	{
		tre[k].v=max(v,tre[k].v);
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)
	{
		if(!tre[k].l)
			tre[k].l=++tot;
		update(tre[k].l,l,mid,x,v);
	}
	else
	{
		if(!tre[k].r)
			tre[k].r=++tot;
		update(tre[k].r,mid+1,r,x,v);
	}
	push_up(k);
}

int query(int k,int l,int r,int L,int R)
{
	if(l>=L&&r<=R) return tre[k].v;
	int mid=l+r>>1,ans=0;
	if(L<=mid)
		if(tre[k].l)
			ans=max(ans,query(tre[k].l,l,mid,L,R));
	if(R>mid)
		if(tre[k].r)
			ans=max(query(tre[k].r,mid+1,r,L,R),ans);
	return ans;
}

int main()
{
	int n;tre[++tot].v=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	update(1,1,n,a[1],1);
	dp[1]=1;int ans=0;
	for(int i=2;i<=n;i++)
	{
		int x=query(1,1,n,0,a[i]-1);
		dp[i]=x+1;
		update(1,1,n,a[i],dp[i]);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
}

简单题练习

云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)