https://blog.csdn.net/tenkuo/article/details/162425738

看到标签是个二分于是来写个题解，虽然最后用的是 dp。

说实话看了十分钟题面样例都没看懂。

题面描述的太复杂了，我们来简化一下题面。

题目大意：

给你 $n$ 个数，$i$ 是第 $a_i$ 个入栈的，是第 $b_i$ 个出栈的，求最少要多少个站才能保证出入栈顺序。（其实用站和栈都是一样的，意思差不多）

思路：

了解了题面之后，我们考虑怎么来做这个题，我们首先按照 $a_i$ 给 $b_i$ 排序，答案就是排完序后 $b$ 的最长上升子序列的长度。为什么呢？因为栈是一个先进后出的结构，也就是你入栈的早，你出栈的就晚，也就是我们需要把排完序后的 $b$ 分成若干个子序列使得子序列内单调递减，也即是求 $b$ 的最长上升子序列。（不知道为啥的看下面有证明）

于是我们容易想到一个 $\Theta(n^2)$ 的做法，但是显然会超时，所以我们考虑将 $dp_i$ 记为长度为 $i$ 的上升子序列最后一项最小是多少，于是我们就可以枚举每一个 $b_i$ 找到小于 $b_i$ 下表最大的 $dp_j$，再将 $dp_j=a_i$，于是时间复杂度为 $\Theta(n \log n)$，可以通过此题。

Ac Code：

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define _ read<int>()
#define int long long
#define R register
#define rint register int 
template<class T>inline T read()
{
    R T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
const int N=2e5+10;
int a[N],b[N],dp[N];
signed main()
{
    rint n=_;
    for(rint i=1;i<=n;i++) a[i]=_;
    for(rint i=1;i<=n;i++) b[a[i]]=_;//按照 a[i] 排序
    rint cnt=0;
    for(rint i=1;i<=n;i++)
    {
        rint l=0,r=cnt,mid,ans=-1;
        while(l<=r)
        {
            mid=l+r>>1;
            if(dp[mid]<b[i])
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        if(ans==-1) continue;
        ans++;
        dp[ans]=b[i];
        if(ans>cnt) cnt=ans;
    }
    out(cnt);
    return 0;   
}

（喜拿最优解！）

证明：

为什么把一个序列分成若干子序列使得子序列内单调不减且尽量少，答案就是最长上升子序列呢？

我们考虑反证：

我们简单的来讲，一个长度为 $m$ 最长上升子序列一定是形如：

的一个序列，那么任意一个子序列（指分成若干份单调不减）都最多只覆盖一个 $q_i$，这是为什么呢？因为子序列的下表是单调递增的所以如果有一个 $j$ 满足 $i<j$ 且 $p_i \ge p_j$ 那就和前面的定义矛盾了，所以假设不成立。