樹狀數組維護LIS--------------------思維(樹狀數組)

注意: 必要時需要離散化

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10000;
int c[N];
int n,a[N];
int f[N];
int lowbit(int x)
{
	return x&(-x);
}
void  add(int i,int val)
{
	while(i<N)
	{
		c[i]=max(c[i],val);
		i+=lowbit(i);
	}
}
int sum(int i)
{
	int res=0;
	while(i)
	{
		res=max(res,c[i]);
		i-=lowbit(i);
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=sum(a[i])+1;
		add(a[i],f[i]);
	}
	for(int i=1;i<=n;i++) cout<<f[i]<<endl;
}