#C240120C. 删数字(number)

标签（Label）

动态规划
树状数组
值域转下标

前言（Front talk)

重在“转化”。

网址（Website）

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

题解 - 删数字(number) - Super

题目（Problem）

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

范围：$1\le n\le 2\times 10^5$；$1\le a[i]\le n$

题解（Solution）

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

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

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

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

代码（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;
}