P6564

标签：ch int res bool P6564 id getchar

#include<bits/stdc++.h>
using namespace std;
inline int read(){int x=0;bool f=0;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return f?-x:x;}
int n,ans,c[200005],f[200005];
struct node {
	int x,id;
} a[200005];
inline void modify(int x,int val){
	while(x<=n)c[x]=max(c[x],val),x+=x&-x;
}
inline int query(int x){
	int res=0;
	while(x>0)res=max(res,c[x]),x-=x&-x;
	return res;
}
inline bool cmp(node A,node B){
	return (A.id-A.x == B.id-B.x)?(A.id<B.id):(A.id-A.x< B.id-B.x );
}
signed main(){
	n=read();
	for(register int i=1;i<=n;i++)a[i].x=read(),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(register int i=1;i<=n;i++){
		if(a[i].id-a[i].x<0)continue;
		int res=query(a[i].x-1)+1;modify(a[i].x,res);
		ans=max(ans,res);
	}
	cout<<ans<<endl;
	return 0;
}

标签：ch,int,res,bool,P6564,id,getchar
From： https://www.cnblogs.com/zan-mei-tai-yang/p/18493156