#C240120C. 删数字(number)

前言（Front talk)

重在“转化”。

网址（Website）

题目详情 - 删数字(number) - Super

题解 - 删数字(number) - Super

题目（Problem）

大意：给出一个序列，删去其中的一些数字，是满足的数字个数最多。输出这个个数。

范围：；

题解（Solution）

重点：最终答案分析法（从结果分析）

删除一些数后，最终的序列中对答案有贡献的数一定满足：

1. 对于该数所在原序列：若，则一定不是有贡献的数；反之，所有有贡献的数一定满足；
2. 对与最终序列中任意两个数：设其在原序列中的位置为和满足，则有且；
3. 易知当满足且时，必定成立，因此可以将该题转化为一道求最长不下降子序列的问题（即且），用树状数组优化求解即可。

备注：树状数组优化求解可以参考数星星。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 101234;
const int inf = N-5;
int n,ans,a[N];
struct Tr{int id,num;}f[N];
int tot;

inline bool cmp(Tr A,Tr B){return A.id==B.id?A.num<B.num:A.id<B.id;}

#define lbt(x) (x&-x)
int c[N<<1];void update(int x,int v){for(int i=x;i<=n;i+=lbt(i))c[i]=max(c[i],v);}
inline int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res=max(res,c[i]);return res;}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("number");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout); 
	cin>>n;For(i,1,n) a[i]=input();
	For(i,1,n){
		if(a[i]>i) continue;tot++;
		f[tot]={i-a[i],a[i]};
	}sort(f+1,f+tot+1,cmp);
	For(i,1,tot){
		int d=1+ask(f[i].num-1);
		update(f[i].num,d);
		ans=max(ans,d);
	}cout<<ans<<'\n';
	return 0;
}