[CF1223D] Sequence Sorting

有 (n) 个数的序列，每次操作可以选择一种数，将他们全部移到开头或结尾，问最少需要多少次操作，才能使序列变为非递减序列。

Solution

将每种数出现的最左最右位置记为这个数的出现位置区间

于是我们要找若干个值连续下降的区间，并且位置从左到右依次排布，互不相交

离散化后预处理出区间，然后扫一遍即可

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

#define int long long
const int N = 1000005;

int n,a[N],l[N],r[N],ans;

signed main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--) {
        cin>>n;
        map<int,int> mp;
        for(int i=1;i<=n;i++) l[i]=1e9,r[i]=0,ans=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) mp[a[i]]++;
        int ind=0;
        for(auto i=mp.begin();i!=mp.end();i++) i->second=++ind;
        for(int i=1;i<=n;i++) a[i]=mp[a[i]];
        for(int i=1;i<=n;i++) l[a[i]]=min(l[a[i]],i), r[a[i]]=max(r[a[i]],i);
        int cnt=0,pos=0;
        for(int i=1;i<=ind;++i) {
            if(l[i]>pos) {
                ++cnt;
            }
            else {
                cnt=1;
            }
            pos=r[i];
            ans=max(ans,cnt);
        }
        cout<<ind-ans<<endl;
    }
}