P1020 [NOIP1999 提高组] 导弹拦截

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

#define int long long
const int N = 1e5 + 10;

int n;
int a[N];
int q[N];

signed main() {
	
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int x;
	while(cin >> x) a[++n] = x;

	int len = 0;
	q[0] = 2e9;   //满足单调递减

	//对于每一个元素，有两种选择
	for(int i = 1; i <= n; i ++) {
		//1.当前元素满足单调性
		if(a[i] <= q[len]) q[++len] = a[i];
		//2.当前元素不满足单调性
		else {
			int l = 1, r = len;
			while(l < r) {
				int mid = l + r >> 1;
				if(q[mid] < a[i]) r =mid;
				else l =mid + 1;
			}
			q[l] = a[i];  //找第一个小于等于他的元素，进行覆盖
		}
	}
	cout << len << endl;   //求最大不升子序列

	len = 0;
	q[0] = -2e9;  //满足单调递增

	//对于每一个元素有两种选择
	for(int i = 1; i <= n; i++) {
		//1.如果当前元素大于其他系统的结尾高度
		if(a[i] > q[len])  q[++len] = a[i];  //分配到新的系统

		else {
			int l = 1, r = len;
			while(l < r) {
				int mid = l + r >> 1;
				if(a[i] <= q[mid]) r = mid;
				else l = mid + 1;
			}
			q[l] = a[i];
		}
	}
	cout << len << endl;
	return 0;
}