引言

参考资料：2009 年集训队论文，徐源盛，《对一类动态规划问题的研究》。

果然我看题解还是看不懂的吗，还是看原论文清楚。（虽然原论文格式排版很难受）

为了方便起见，以下认为编号为 $x$ 的人应当放到第 $x$ 号位置，下标从 $0$ 到 $n-1$。

为了方便起见，我们再在第 $n$ 项放入一个 $n$，减少讨论。

以下把重标号后的序列记为 $\{a\}$。

思路

摆结论

$\textbf{Fact 1}$ 每个人最多被选择并移动一次。

$\textbf{Fact 2}$ 总存在按编号递减序移动取到最优解的方案；如果一个人被移动，总可令其移动到比其编号大 $1$ 的人之前，使得答案仍可取最优。

这两条结论的证明不是重点，此处从略。

由这两条结论，我们得到，按照如下做法进行操作是可获得最优解的：

• 按编号从大到小枚举每个人，考虑其是否主动移动。假设当前枚举到编号为 $x$ 的人。
• 如果其主动移动，其会移动到当前编号为 $x+1$ 的人前面。
• 否则，若其不主动移动，会导致对于编号更小的人，其移动方案的局面发生改变。
• 注意如果当前节点在 $x+1$ 右边，其必须主动移动。

然后我们得到一个推论，也即：

假设当前处理的是节点 $x$，则所有 $\le x$ 的数相对顺序不变，所有大于 $x+1$ 的数顺次排列在 $x+1$ 之后（但是不一定紧邻）。

主动移动的贡献

我们现在先只考虑每一步都仅仅只有主动移动的情况。

假设原序列中 $x$ 在 $p$ 号位置，则现在其所在的位置为 $\sum_{i=0}^{p-1}[a_i<x]$，对答案有 $1+\sum_{i=0}^{p-1}[a_i<x]$ 的贡献。

问题是，现在 $x+1$ 在哪里是未知的，不妨假设现在其在 $t$ 号位置，显然 $t\le x$；因此容易发现，总存在一个位置 $q$，使得 $\sum_{i=0}^{q-1}[a_i<x+1]=t$。因此我们得到，现在的 $x+1$ 的位置就等效于原序列中的 $q$ 号位置，因为我们可以使用与 $x$ 相同形式的公式来从位置 $q$ 推算出 $x+1$ 现在所在位置 $t$。为了后面 dp 方便，我们这里采用 $q$ 来描述其目前位置。

这样，此次移动总贡献容易发现即为 $\sum_{i=0}^{p-1}[a_i<x]+\sum_{i=0}^{q-1}[a_i<x+1]+1$。

问题是，这个等效坐标 $q$ 怎么选取呢？或者说，如果把 $q$ 记入状态，那么状态怎么转移呢？

答案是，直接用现在的 $q$ 做新的 $q$！

为什么？

考虑到移动相对位置不方便，我们考虑把问题转化为等效的绝对坐标，然后说明绝对坐标就是一个合法的等效坐标。

譬如，如果当前序列为

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline2&1&4&0&3&5\\\hline\end{array} $$

考虑保留格子，而仅修改每个元素的位置。

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline2&1&\varnothing&0&3&4,5\\\hline\end{array} $$$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline2&1&\varnothing&0&\varnothing&3,4,5\\\hline\end{array} $$$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline\varnothing&1&\varnothing&0&\varnothing&2,3,4,5\\\hline\end{array} $$$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline\varnothing&\varnothing&\varnothing&0&\varnothing&1,2,3,4,5\\\hline\end{array} $$$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline\varnothing&\varnothing&\varnothing&\varnothing&\varnothing&0,1,2,3,4,5\\\hline\end{array} $$

这是连续做了 $4$ 次后的结果。

容易观察发现，由于考虑到 $x$ 放到 $x+1$ 前一位后，$t$ 不改变，而 $q$ 和 $t$ 的关系式中 $x+1$ 变为 $x$ 答案不变，于是 $q$ 可以保持相同。

简单说来，记考虑了 $x\sim n$，并且 $x$ 的等效坐标为 $q$ 的最优解为 $f(x,q)$，则贡献转移方向为

$$f(x,q)\leftarrow f(x+1,q)+\sum_{i=0}^{p-1}[a_i<x]+\sum_{i=0}^{q-1}[a_i<x+1]+1 $$

为了再考虑到 $x$ 在 $x+1$ 右侧的情况，应当调整为

$$f(x,q)\leftarrow f(x+1,q)+\sum_{i=0}^{p-1}[a_i<x]+\sum_{i=0}^{q-1}[a_i<x]+2 $$

不选择移动的贡献

显然得有 $p<q$。否则最后不能自然拼合。

结论是类似的。

但是贡献不能单独计算本次的（本次本身没有贡献）。

考虑到会有将来的费用，考虑如何计入这部分贡献。

哪部分贡献呢？

其实考虑一下，会发现就是说，考虑到，我们上面的 dp 是建立在每一步都仅仅只有主动移动的基础上的，我们要通过附加的贡献，使得后面计算 $\sum_{i=0}^{p-1}[a_i<x]$ 的部分是等效正确的。

显然，要计算的贡献，即是在 $p$ 右边、$q$ 左边并且比 $x$ 小的数的数目。

也即，

$$f(x,p)\leftarrow f(x+1,q)+\sum_{p<i<q}[a_i<x]\quad(p<q) $$

但是很不幸，这是假的。

因为 $a_i$ 穿过时，还会多穿过 $a_i+1\sim x-1$，而这部分贡献我们刚刚没有统计！

于是即为

$$f(x,p)\leftarrow f(x+1,q)+\sum_{p<i<q}[a_i<x](x-a_i)\quad(p<q) $$

然后就好了。

Code

Luogu 上的版本要输出方案，随便写一下就好了。

总复杂度 $O(n^2)$。

bzoj 上这个输出格式好神秘……

// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
uint F[1005][1005],From[1005][1005];
uint A[1005],At[1005],Cnt[1005][1005];
const ullt inf=1e9;
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint n;scanf("%u",&n);for(uint i=0;i<n;i++)scanf("%u",A+i),A[i]++,At[i]=i;
    At[n]=n,std::sort(At,At+n+1,[](uint a,uint b){return A[a]>A[b];});
    for(uint i=0;i<=n;i++)A[At[i]]=i;
    for(uint i=0;i<=n;i++)for(uint j=0;j<=n;j++)Cnt[i][j+1]=Cnt[i][j]+(A[j]<i);
    for(uint i=0;i<n;i++)F[n][i]=inf;
    for(uint i=n-1;~i;i--){
        for(uint j=0;j<=n;j++)
            F[i][j]=F[i+1][j]+Cnt[i][At[i]]+Cnt[i][j]+2,From[i][j]=j;
        for(uint j=At[i]+1,v=0;j<=n;j++){
            if(_min(F[i][At[i]],F[i+1][j]+v))
                From[i][At[i]]=j;
            if(A[j]<i)v+=i-A[j];
        }
    }
    uint p=std::min_element(F[0],F[0]+n+1)-F[0];
    std::vector<std::pair<uint,uint> >Ans;std::vector<uint>P;
    for(uint i=0;P.push_back(p),i<n;i++)p=From[i][p];
    for(uint i=0;i<n;i++)if(P[i]==P[i+1]){
        uint p1=Cnt[i][At[i]],p2=Cnt[i+1][P[i+1]];
        for(uint j=i+1;j<=n;j++)p1+=P[j]<At[i];
        for(uint j=i+2;j<=n;j++)p2+=P[j]<P[i+1];
        if(p1<p2)Ans.push_back({p1,p2-1});
        else Ans.push_back({p1,p2});
    }
    std::reverse(Ans.begin(),Ans.end());printf("%u\n",(uint)Ans.size());
    for(auto s:Ans)printf("%u %u\n",s.first+1,s.second+1);
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。