題目鏈接

題意：

給出一個長為 \(n\) 的排列。每一次可以選擇以下的任一操作進行：

1. 交換相鄰的兩個數
2. 將排列中一個數挪到序列開頭
3. 將排列中一個數挪到序列結尾

求使得排列有序的最小總操作次數。

\(n\le 5\times 10^5\)

首先，我們可以發現， 2、3 操作是不受排列的影響的，也就是無論排列長什么樣都可以對任意數進行 2、3 操作。

而且每個數至多會進行一次 2 或 3 操作（2,3 里選一個）。因此我們可以考慮對于哪些數進行 2 操作、哪些數進行 3 操作。

我們發現，如果我們選定了哪些數進行 2 操作，那么我們一定可以將這些數 排好序 并放在開頭。因為進行 2 操作的順序任意。

所以有一個貪心策略：

我們會選定 \((x,y)\) ，對于 \(a_i\le x\) 的 \(i\) 位置進行 2 操作，對于 \(a_j\ge y\) 的 \(j\) 位置進行 3 操作。

先把所有 2,3 操作執行完，使得選中的那些數有序。然后對于剩下的數，用 1 操作解決。

可以發現這樣一定是最優的。

那么現在問題在于，如何找出 \((x,y)\) 滿足 \(x+(n-y+1)+inv(x+1,y+1)\) 的值最小。其中 \(inv(l,r)\) 表示值在 \([l,r]\) 的數之間的逆序對個數。

那么暴力做法可以 \(O(n^2)\) 求。如何優化？

因為值在 \([l,r]\) 的數太過于分散，不好計算逆序對，所以考慮轉變為在值域上計算逆序對。

怎么做呢？設原序列為 \(a\)，我們建立序列 \(id\)，滿足 \(id_{a_i}=i\)。

你會發現原序列中是逆序對的位置在 \(id\) 序列中也是逆序對。而且值在 \([l,r]\) 之間的 \(a\) 的下標都在 \(id\) 數組的 \([l,r]\) 內。

于是我們就將 \(a_i\in[l,r]\) 的 \(i\) 之間的逆序對轉化為了 \(id\) 中在 \([l,r]\) 的逆序對。

所以設 \(inv'(l,r)\) 表示 \(id\) 數組中 \([l,r]\) 的逆序對個數。當 \(l>r\) 時， \(inv'(l,r)=0\)。

則選 \((x,y)\) 的權值為 \(x+(n-y+1)+inv'(x+1,y-1)\)。

我們發現， \((i,j)\) 的權值滿足四邊形不等式。

證明：

設有 \(i,j\in[1,n]\) 滿足 \(i+1\le j-1\)。

要證 \((i,j)+(i+1,j-1)\ge (i+1,j)+(i,j-1)\)。

只要證 \((i,j)-(i,j-1)\ge (i+1,j)-(i+1,j-1)\)

將其拆開，只要證

\[[i+(n-j+1)+inv'(i,j)]-[i+(n-j+2)+inv'(i,j-1)]\\ \ge \\ [i+1+(n-j+1)+inv'(i+1,j)]-[i+1+(n-j+2)+inv'(i+1,j-1)] \]

發現兩邊有很多可以消掉，只要證

\[inv'(i,j)-inv'(i,j-1)\ge inv'(i+1,j)-inv'(i+1,j-1) \]

二者實際上在比較 \(j\) 在 \(inv'(i,j)\) 里貢獻大還是 \(inv'(i+1,j)\) 里貢獻大。因為 \(inv'(i,j)\) 為 \([l,r]\) 逆序對個數，而 \(id_i\) 可能大于 \(id_j\)，貢獻可能多 \(1\)，因此前者是 \(\ge\) 后者的。

所以綜上得證。

于是對于 \(x\) 來說，最優的 \(y\) 具有決策單調性，也就是當 \(x\) 遞增時，最優的 \(y\) 單調不降。

于是就可以用分治去做。但是過程中我們需要求一段區間的逆序對個數，也就是需要快速求 \(inv'(l,r)\)。

神犇 @JDScript0117 的解法是用主席樹維護。

但得益于主席樹的常數，我們還有更快的做法，就是用莫隊+樹狀數組去動態維護。可以發現，左右端點的移動次數都不超過 \(O(n\log n)\) 次，開兩棵樹狀數組，一棵維護前綴和，一棵維護后綴和。

簡略證明莫隊指針挪動次數在 \(O(n\log n)\):

先考慮左端點，每一次的左端點都是 \(mid+1\)，所以在分治過程中移動次數在 \(O(n\log n)\)。

右端點的證明過程有點類似，在計算 \(x=mid\) 時，設決策區間為 \([L,R]\) ，則在這一層中，右端點的挪動次數是 \(O(R-L)\) 的，所以右端點移動總次數可以近似所有決策區間長度之和。所有決策區間之和為 \(O(n\log n)\)。因此右端點移動次數為 \(O(n\log n)\)。

于是就可以做到 \(O(n\log ^2n)\) 將這道題做完了。

主席樹跑了 2000ms 左右，但是莫隊只跑了 1000ms \(\sim\) 1300ms。

代碼：

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
const int N=1e6+5;
#define int long long
#define lowbit(x) (x&(-x))
int sum[N],n,a[N],id[N],ans=1e18,ql=1,qr=0,now,sum2[N];
//sum,sum1分別是維護前、后綴和的樹狀數組
//ql,qr 是莫隊的指針 ，now為當前區間 [ql,qr] 的逆序對個數 
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void update(int pos,int w)
{
	for(int i=pos;i>0;i-=lowbit(i)) sum[i]+=w;
	for(int i=pos;i<=n;i+=lowbit(i)) sum2[i]+=w;
}
int query1(int pos)
{
	int res=0;
	for(int i=pos;i<=n;i+=lowbit(i)) res+=sum[i];
	return res;
}
int query2(int pos)
{
	int res=0;
	for(int i=pos;i>0;i-=lowbit(i)) res+=sum2[i];
	return res;
}
void get(int l,int r)//莫隊 
{
	if(qr<l||ql>r)//如果完全不在區間內，還不如直接清空，跳到目標區間去
	{
		for(int i=ql;i<=qr;i++) update(id[i],-1);
		now=0;
		for(int i=l;i<=r;i++) now+=query1(id[i]),update(id[i],1);
		ql=l,qr=r;
		return;
	}
	while(qr>r) update(id[qr],-1),now-=query1(id[qr]),qr--;
	while(qr<r) qr++,now+=query1(id[qr]),update(id[qr],1);
	while(ql>l) ql--,now+=query2(id[ql]),update(id[ql],1);
	while(ql<l) update(id[ql],-1),now-=query2(id[ql]),ql++;
}
void solve(int l,int r,int L,int R)//分治 
{//表示當 x 在 [l,r] 內時，最優的 y 在 [L,R] 內 
	if(l>r) return;
	int mid=(l+r)>>1,res=n,k=mid;
	for(int i=max(mid+1,L);i<=R;i++)//直接求最優決策點 
	{
		get(mid+1,i);
		int w=now+mid+(n-i);
		if(w<res) k=i,res=w;
	}
	ans=min(ans,res);
	solve(l,mid-1,L,k);//向下遞歸 
	solve(mid+1,r,k,R);
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),id[a[i]]=i;
	solve(0,n,1,n);
	printf("%d\n",ans);
	return 0;
}