【Codeforces 1367F】 Flying Sort (Hard Version)

【题意】

给定一个正整数序列（$n\le 2\times 10^5$）。每次操作可将任意一个数字移动至序列最开始或最末尾。求使得序列不降所需的最少操作次数。

【分析】

注意到给定的序列中一定有一个子序列是最后不降序列的一部分。所以，如果我们能确定这个部分，就可以比较轻松地解决这个问题。
所以原问题转化为：求原序列与所得的最长公共子序列。注意到这个公共子序列只能有下图的三部分：

所以考虑用三个数组来进行dp：$f[i]$为以i为结尾的最长公共子序列长度，$g[i]$为以i为结尾的包含第一个$a[i]$的最长公共子序列长度。$s[i]$为至今为止i出现的次数，则
$$\begin{gathered} g[i]=max(s[a[i]],s[a[i]-1]+1),s[a[i]]=1 \\ g[i]=g[las[a[i]-1]]+1,s[a[i]]=1\&后面没有a[i]-1 \\ g[i]=g[las[a[i]]]+1 \\ f[i]=max(g[i],g[las[a[i]-1]]+1),后面没有a[i]-1 \\ f[i]=f[las[a[i]]]+1 \end{gathered}$$
其中，$g[i]$存在的目的是保证求得的最长公共子序列满足中间那一段的性质。

#include
using namespace std;
const int mn = 200005;
int f[mn], a[mn], l[mn], r[mn], s[mn], seq[mn], cnt, g[mn], las[mn];
int main()
{
   int T, n;
   scanf("%d", &T);
   while(T--)
   {
       scanf("%d", &n);
       for(int i = 1; i <= n; i++)
       {
           scanf("%d", &a[i]), seq[i] = a[i];
           l[i] = n + 1, r[i] = s[i] = f[i] = g[i] = h[i] = las[i] = 0;
       }
       sort(seq + 1, seq + 1 + n);
       cnt = unique(seq + 1, seq + 1 + n) - seq - 1;
       for(int i = 1; i <= n; i++)
       {
           a[i] = lower_bound(seq + 1, seq + 1 + cnt, a[i]) - seq;
           l[a[i]] = min(l[a[i]], i), r[a[i]] = max(r[a[i]], i);
       }
       for(int i = 1; i <= n; i++)
       {
           ++s[a[i]];
           if(s[a[i] - 1])
           {
               if(i == l[a[i]])
                   g[i] = max(s[a[i] - 1] + 1, g[i]);
               f[i] = max(f[i], s[a[i] - 1] + 1);
               if(i == l[a[i]] && i >= r[a[i] - 1])
                   g[i] = max(g[i], g[las[a[i] - 1]] + 1);
               if(i >= r[a[i] - 1])
                   f[i] = max(f[i], g[las[a[i] - 1]] + 1);

           }
           if(s[a[i]] > 1)
           {
               g[i] = max(g[i], g[las[a[i]]] + 1);
               f[i] = max(f[i], f[las[a[i]]] + 1);
           }
           g[i] = max(g[i], s[a[i]]);
           f[i] = max(f[i], g[i]);
           las[a[i]] = i;
       }
       printf("%d\n", n - *max_element(f + 1, f + 1 + n));
   }
}