线段树 20 pts 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n, ans, y, tree[4 * maxn];
struct Node{
	int id, v;
	void input()
	{
		cin >> v;
	}
	bool operator <(const Node &o) const{
		if (o.id - o.v == id - v)
		{
			return id < o.id;
		}
		return id - v < o.id - o.v;
	}
}a[maxn];
int ls(int x)
{
	return 2 * x;
}
int rs(int x)
{
	return 2 * x + 1;
}
void up(int x)
{
	tree[x] = max(tree[ls(x)], tree[rs(x)]);
}
void update(int x, int l, int r, int p, int k)
{
	if (l == r)
	{
		tree[x] = max(tree[x], k);
		return;
	}
	int mid = (l + r) / 2;
	if (p <= mid)
	{
		update(ls(x), l, mid, p, k);
	}
	if (p >= mid + 1)
	{
		update(rs(x), mid + 1, r, p, k);
	}
	up(x);
	return;
}
int query(int x, int l, int r, int p)
{
	if (l == r)
	{
		return tree[x];
	}
	int mid = (l + r) / 2, ret;
	if (p <= mid)
	{
		ret = query(ls(x), l, mid, p);
	}
	if (p >= mid + 1)
	{
		ret = query(rs(x), mid + 1, r, p);
	}
	return ret;
} 
signed main()
{
	cin >> n;
	for (int i = 1; i <= n; ++ i)
	{
		a[i].input();
		a[i].id = i;
		y = max(y, a[i].v);
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++ i)
	{
		if (a[i].v > a[i].id)
		{
			continue;
		}
		int h = query(1, 1, y, a[i].v - 1) + 1;
		update(1, 1, y, a[i].v, h);
		ans = max(ans, h);
	}
	cout << ans;
	return 0;
}