求序列中最长不升子序列的长度和不升子序列的个数

狄尔沃斯定理（Dilworth's theorem）

该定理表述为：在一个有限的偏序集 P 中，最大抗链的大小等于最小覆盖的大小。换句话说，若 P 是一个有限的偏序集，且 α 是 P 中的一个最大抗链（即其中任意两个元素不可比较），而 β是 P 的一个最小覆盖（即覆盖所有元素的最小链），则有：∣α∣=∣β∣

在一个给定的序列中，最长递增序列的长度与不升序列的个数之间存在一种对偶关系。具体来说，若我们考虑一个有限的偏序集，其中元素的比较关系是基于大小关系的，那么：

不升序列的个数可以看作是一个抗链的大小。

最长递增序列的长度可以看作是一个链的大小。

采用二分贪心来解决，时间复杂度为O(nlogn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> heights;
vector<ll> stk1;
vector<ll> stk2;

void solve() {
	for(ll height : heights) {
		if(stk1.empty()) {
			stk1.push_back(height);
		} else {
			if(stk1.back() >= height) {
				stk1.push_back(height);
			} else {
				auto pos = upper_bound(stk1.begin(), stk1.end(), height, [](const ll &u, const ll &v) {return u > v;});
				*pos = height;
			}
		}
		if(stk2.empty()) {
			ans.push_back(height);
		} else {
			if(stk2.back() < height) {
				ans.push_back(height);
			} else {
				auto pos = lower_bound(stk2.begin(), stk2.end(), height);
				*pos = height;
			}
		}
	}
	cout << stk1.size() << '\n' << stk2.size();
}

int main()
{
	ll height;
	while(cin >> height) {
		heights.push_back(height);
	}
	solve();
	return 0;
}