5min 秒了。

xixisuper：多打 ABC 多见原题。

首先是一个常见题意转化，交换相邻元素使序列变有序的最小次数等价于数这个序列的逆序对个数。

但是这题让求变成循环同构序列的的最小交换次数，怎么做呢？

考虑一种映射，假设我们的目标序列是 $a=\{x,x+1,\cdots,n,1,2\cdots x-1\}$，那么我们把 $a_i\to i$ 上，就又变成了求逆序对个数了。

最后考虑如何实现这种映射，不难想到的是先令让值域变成 $0\sim n-1$，然后映射就相当于是把 $a_i\to (a_i+k)\bmod n$ 上。

最后我们对于 $k\in[0,n-1]$ 中的每一个 $k$ 求出对应的操次数，然后输出最小值就是答案。

而转化后的题目实际上就是ABC396F，。

转化后怎么做呢？考虑任意两位之间的贡献：

当 $k$ 属于上述蓝色箭头部分时会产生贡献。

贡献等价于蓝色箭头部分的贡献减去橙色部分箭头的贡献。

用树状数组计算贡献，然后改变差分数组即可，时间复杂度 $O(n\log n)$。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=4e5+10;
inline ll lowbit(ll x){return x&(-x);}
ll sum[N];
void add(ll x){for(ll i=x;i<N;i+=lowbit(i)) sum[i]+=1;}
ll query(ll x){
	ll ret=0;
	for(ll i=x;i;i-=lowbit(i)){ret+=sum[i];}
	return ret;
}
void init(){for(ll i=0;i<N;i++) sum[i]=0;}
ll n,m,a[N],cha[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;m=n;
	for(ll i=1;i<=n;i++){cin>>a[i];a[i]--;}
	for(ll i=n;i>=1;i--){
		add(a[i]+1);
		ll dt=query(a[i]);
		cha[0]+=dt;
		cha[m-a[i]]-=dt;
		dt=query(m+1)-query(a[i]+1);
		cha[m-a[i]]-=dt;
	}
	init();
	for(ll i=1;i<=n;i++){
		add(a[i]+1);
		ll dt=query(m+1)-query(a[i]+1);
		cha[m-a[i]]+=dt;
		dt=query(a[i]);
		cha[m-a[i]]+=dt;
	}
	ll ans=cha[0];
	for(ll i=1;i<m;i++){
		cha[i]+=cha[i-1];
		ans=min(ans,cha[i]);
	}
	cout<<ans;
	return 0;
}

题意

给你一个1-n的排列，每次只允许你交换任意两个相邻的元素，问最少多少次交换可以得到 1, 2, 3, ..., n 的一个循环同构序列

同构序列指任意i满足(a[i] + 1) % n = a[i+1]的序列

做法

原题意其实等价于前n小的数加n后最少逆序对个数

举个例子

对原序列3 5 4 2 1求逆序对

等价于将序列排成1 2 3 4 5的最小次数

然后将最小的那个加n

即对3 5 4 2 6求逆序对

等价于将原序列排成2 3 4 5 1的最小次数

我们可以发现变化一次就等价于将原序列的逆序对加(n - b[i]) - (b[i] - 1) b[i]指数值为i的位置 b[3] = 1

为什么呢

我们每次改变的值都是当前序列的最小值,所以他左侧的值和右侧的值都大于他，所以左侧一定会减少(b[i] - 1)个逆序对，他加上n后一定是整个序列的最大值，右侧一定会增加(n - b[i])

所以这个题就做完了

code

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

const long long N = 1e5 + 10;

long long n, a[N], b[N];

void read(){
	cin >> n;
	for(long long i = 1;i <= n; i++){
		cin >> a[i];
		b[a[i]] = i;
	}
	return ;
}

struct tree{
	long long w[N], n;
	long long lb(long long x) {return x & -x;}
	long long qry(long long i){long long res = 0; for(;i;i -= lb(i)) res += w[i]; return res;}
	void add(long long i,long long x){for(;i <= n; i += lb(i)) w[i] += x;}
	void clear(){for(long long i = 1;i <= n; i++) w[i] = 0;}
}t;

void compute(){
	t.n = n;
	long long ans = 0;
	for(long long i = n;i >= 1; i--){
		ans += t.qry(a[i]);
		t.add(a[i],1);
	}
	long long now = ans;
	for(long long i = 1;i <= n; i++){
		now += (n - b[i]) - (b[i] - 1);
		ans = min(ans,now);
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}