【SSL1459】求最长不下降子序列【树状数组】

重操旧业

离散化 + + +树状数组
离散化啥的可以用 p a i r pair pair

#include
#include
#include
#include
#include
#define reg register
using namespace std;
typedef long long ll;
const int N=1005;
int n,f[N],ans,c[N];
pair a[N];
int lowbit(int x){return x&(-x);}
void update(int x,int k)
{
	for(;x<=n;x+=lowbit(x))
		c[x]=max(k,c[x]);
}
int find(int x)
{
	int res=0;
	for(;x;x-=lowbit(x))
		res=max(res,c[x]);
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		a[i].first=x;
		a[i].second=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		f[i]=find(a[i].second)+1;
		update(a[i].second,f[i]);
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,f[i]);
	printf("%d",ans);
    return 0;
}