5644. 得到子序列的最少操作次数

5644. 得到子序列的最少操作次数

可以转化为求最长公共子序列问题。
但是题目上数据范围是1e5，题目又有条件target数组是不重复的，最长公共子序列的做法是dp，复杂度为。
所以可以将LCS问题转化为求LIS问题，后者可以用栈优化使复杂度降到

如果没有target中不重复这个条件，就只能使用的dp求LCS问题了

那个二分还是需要注意点的。就是关于求LIS时候的那个栈，q[0]是不用的，len代表的是从[1,len]左右都闭，长度就是len了，栈最顶端的元素下标也是len。
二分部分的代码等价于这一行

int r=lower_bound(q.begin()+1,q.begin()+len+1,a[i])-q.begin()-1;

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int,int>pos;
        for(int i=0;i<target.size();i++){
            pos[target[i]]=i;
        }

        vector<int>a;

        for(auto i:arr)
            if(pos.count(i))
                a.push_back(pos[i]);
        vector<int>q(a.size()+1);
        int len=0;
        for(int i=0;i<a.size();i++){
            int l=0,r=len;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(q[mid]<a[i])l=mid;
                else r=mid-1;
            }
            len=max(len,r+1);
            q[r+1]=a[i];
        }
        return target.size()-len;
    }
};