用二分维护 LIS 的单调递增性

看题解里是 f[l] = min(f[l], a[i]);

Q1. 二分后已经保证了 $f[l] \geqslant a[i]$ ，不直接 f[l] = a[i]; 就行了嘛？

Q2.这样的话，可能会导致实际所求的 LIS 数列每个数的序号不是严格单调递增的；

例如：

3
2 3 1

如果查看运行过程，如下：

3
2 3 1
i = 3
l = 0 r = 2 mid = 1
l = 0 r = 1 mid = 0
ans = 1
1 3
2

可以看到，实际所得的 LIS 是 13，不是 23 ？

然后我就此改经了一下，增加一个记录序号的数组并将替换条件修改：

f[l] = min(f[l], (l < len && id[a[i]] > id[f[l+1]] ? f[l] : a[i]));

解决了序号可能不是严格单调递增的问题

但是会 wa ，为什么？

#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 1e6 + 10, inf = 0x3f3f3f3f;
int n, a[N], f[N];
int id[M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		id[a[i]] = i;
		f[i] = inf;
	}
	f[1] = a[1];
	int len = 1;
	for (int i = 2; i <= n; i ++)
	{
		int l = 0, r = len;
		if (a[i] > f[len]) f[++len] = a[i];
		else
		{
//			printf("i = %d\n", i);
			while (l < r)
			{
				int mid = (l + r) >> 1;
//				printf("l = %d r = %d mid = %d\n", l, r, mid);
				if (f[mid] >= a[i]) r = mid;
				else l = mid + 1;
			}
//			printf("ans = %d\n", l);
			f[l] = min(f[l], a[i]);
//			f[l] = min(f[l], (l < len && id[a[i]] > id[f[l+1]] ? f[l] : a[i]));
//			for (int j = 1; j <= len; j ++) printf("%d ", f[j]);
//			printf("\n");
		}
	}
	cout << len;

	return 0;
}