思路

不上升序列

我们用数组d1当作栈来存储它。

遍历导弹高度，把栈顶元素和高度比较：

1. 若 ai≤d.length，此时 ai 是符合要求的，直接入栈。
2. 若 ai>d.length，此时 ai 把栈内第一个小于它的覆盖掉。这里说一下，能够覆盖它是因为我们不需要再访问它的值了。在测试数据中，此后几次都会进行这一操作，如果仅仅取这几个数据，最长不上升子序列长度仍然正确； 取所有数据，几次操作之后，就会执行操作1，结果仍然正确。

上升序列

和不上升序列一样，只不过把 upper_bound 改为了 lower_bound，因为会出现两个相同高度的导弹的情况，这两个导弹仅仅需要同一的炮弹去拦截。

AC代码

#include <bits/stdc++.h>
using namespace std;
int a[100001], n = 0, d1[100001], d2[100001], c1 = 0, c2 = 0;
int main()
{
    while (cin >> a[n])
		n++;
    d1[0] = a[0], d2[0] = a[0];
    for (int i = 1; i < n; i++)
	{
        if (a[i] <= d1[c1])
            d1[++c1] = a[i];
        else
		{
            int x = upper_bound(d1, d1 + c1, a[i], greater<int>()) - d1;
            d1[x] = a[i];
        }
        if (a[i] > d2[c2])
            d2[++c2] = a[i];
        else
		{
            int x = lower_bound(d2, d2 + c2, a[i]) - d2;
            d2[x] = a[i];
        }
    }
    cout << c1 + 1 << endl << c2 + 1;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=10000000;
int x,n,a[N],f[N],d[N],ans;
int max_len(int x)
{
	int l=1,r=n,mid,ans;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(d[mid]<x)
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	return ans;
}
int main()
{
	while(cin>>x)
		a[++n]=x;
	for(int i=1;i<=n;i++)
	{
		int now=max_len(a[i]);
		d[now]=a[i];
		f[i]=now;
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	memset(f,0,sizeof(f));
	memset(d,1000000,sizeof(d));
    ans=0;
	for(int i=1;i<=n;i++)
	{
		int now=lower_bound(d+1,d+n+1,a[i])-d;
		d[now]=a[i];
		f[i]=now;
		ans=max(ans,f[i]);
	}
	cout<<ans;
}

`

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
int n, f[MAXN], a[MAXN], b[MAXN], od[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    while (cin >> b[n]) {
        n++;
    }
    reverse(b, b + n);
    f[1] = b[0];
    int curn = 1;
    for (int i = 1; i < n; i++) {
        if (b[i] >= f[curn]) {
            f[++curn] = b[i];
        } else {
            f[upper_bound(f + 1, f + curn + 1, b[i]) - f] = b[i];
        }
    }
    cout << curn << endl;

    reverse(b, b + n);
    f[1] = b[0];
    curn = 1;
    for (int i = 1; i < n; i++) {
        if (b[i] > f[curn]) {
            f[++curn] = b[i];
        } else {
            f[lower_bound(f + 1, f + curn + 1, b[i]) - f] = b[i];
        }
    }
    cout << curn << endl;
    return 0;
}

while (cin >> x)
        a[++n] = x;
    memset(d, 0x3f, sizeof(d));
    reverse(a+1, a+n+1);
    f[1] = a[1];
    for (int i = 1; i < n; i++)
    {
        if (a[i] >= f[ans])
            f[++ans] = a[i];
        else
            f[upper_bound(f + 1, f + ans + 1, a[i]) - f] = a[i];
    }//正常的LIS
    reverse(a+1, a+n+1);
    for (int i = 1; i <= n; i++)
    {
        int now = lower_bound(sta+1, sta+num+1, a[i])-sta;
        if (now == num + 1)
            sta[++num] = a[i];
        else sta[now] = a[i];
    }

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
int n, f[MAXN], a[MAXN], b[MAXN], od[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    while (cin >> b[n]) {
        n++;
    }
    reverse(b, b + n);
    f[1] = b[0];
    int curn = 1;
    for (int i = 1; i < n; i++) {
        if (b[i] >= f[curn]) {
            f[++curn] = b[i];
        } else {
            f[upper_bound(f + 1, f + curn + 1, b[i]) - f] = b[i];
        }
    }
    cout << curn << endl;

    reverse(b, b + n);
    f[1] = b[0];
    curn = 1;
    for (int i = 1; i < n; i++) {
        if (b[i] > f[curn]) {
            f[++curn] = b[i];
        } else {
            f[lower_bound(f + 1, f + curn + 1, b[i]) - f] = b[i];
        }
    }
    cout << curn << endl;
    return 0;
}