自动搬运

查看原文

来自洛谷，原作者为

	zhiyangfan 诶嘿~

搬运于2025-08-24 21:44:12，当前版本为作者最后更新于2022-02-25 16:56:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P2995 [USACO10NOV]Cow Photographs G

很有意思的一道题，正好初学群论，写一点从置换角度的理解。

题意

给出一个 $(1,2,\cdots,n)$ 的排列 $\mathrm{p}$，求出 $\mathrm{p}$ 最少交换多少次相邻元素能够与 $(1,2,\cdots,n)$ 循环同构。($1\le n\le 10^5$)

题解

首先要知道怎么求出两个排列 $\mathrm{p,q}$ 之间的最小交换次数。考虑一个置换：

$$p=\begin{pmatrix}\mathrm{p}\\1,2,\cdots,n\end{pmatrix} $$

即把排列 $\rm p$ 对应到“标准”排列的置换，则对排列 $\rm q$ 做置换 $p$ 会得到一个新的排列 $\rm q'$，而 $\rm p,q$ 之间的最小交换次数即 $\rm q'$ 中的逆序对个数。这个问题可以这么理解，我们把 $\rm p,q$ 都对应到了“标准”排列，每次交换相当于交换“标准”排列，而“标准”排列满足一开始没有逆序对，每次交换会增加一个逆序对，这样的话，$\rm q'$ 中的逆序对个数就是交换次数。

现在考虑这道题怎么做，考虑枚举最终要到达的排列，即所有 $n$ 个与 $(1,2,\cdots,n)$ 循环同构的排列。如果我们令最终排列 $\mathrm{p}_i$ 为：

$$\mathrm{p}_i=(2-i,3-i,\cdots,n+1-i)$$

其中定义 $1-1=n$。这样的话，$\mathrm{p}_i$ 对应的置换即：

$$p_i=\begin{pmatrix}2-i,3-i,\cdots,n-i+1\\1,2,\cdots,n\end{pmatrix} $$

考虑把这个置换施加到 $\rm q$ 上的效果，将 $p_i$ 施加到 $\rm q$ 身上，相当于将 $\rm q$ 上的所有元素循环减一：

$$\mathrm{q}\times p_i=(\mathrm{q}_1-i+1,\mathrm{q}_2-i+1,\cdots,\mathrm{q}_n-i+1) $$

减法定义同上。这样的话，如果能在合理时间内求出 $\rm q$ 每次置换后的逆序对，取个 $\min$ 即得答案。

注意到这个过程是依次相减的过程，所以我们考虑找出每次置换引起的逆序对变化。首先我们先求出 $\mathrm{q}\times p_1$，即原排列的逆序对，然后考虑将原排列循环减一后会发生什么。发现所有值会分为两种，一种是单纯的减一，另一种是在减到 $0$ 后又回到 $n$，而后者显然只有 $1$ 这个元素满足。对于前者，它们之间的逆序对是不会改变的，毕竟都减一了，相对大小是不改变的。对于后者，它和其他元素的大小关系会颠倒，即如果设它的位置为 $l$，则 $[1,l)$ 位置上的元素原来均和它形成逆序对，现在均不形成，需要减去，而 $(l,n]$ 位置上的元素原来均和它不形成逆序对，现在均形成，需要加上。也就是说，逆序对会增加 $n-l-(l-1)$ 个。

现在我们来考虑怎么求出 $l$。注意到一次置换会把所有数都循环减 $1$，所以 $\mathrm{q}\times p_i$ 后，那个出现循环的 $1$ 位置应在原排列的 $i-1$ 所在位置。所以我们记录下原排列中每个值对应的位置，求出 $\mathrm{q}\times p_1$ 的逆序对，然后枚举 $p_2\sim p_n$，分别处理逆序对的变化即可。时间复杂度 $\mathcal{O}(n\log n)$。

#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10; int a[N], p[N], pos[N]; typedef long long ll;
inline void read(int& x)
{
    x = 0; char ch; int f = 1;
    while ((ch = getchar()) < '0' || ch > '9') f = (ch ^ '-' ? 1 : -1);
    while (x = (x << 1) + (x << 3) + ch - '0', (ch = getchar()) >= '0' && ch <= '9') ;
    x *= f;
}
struct BIT
{
    ll c[N]; int len;
    int lowbit(int x) { return x & -x; }
    void add(int x, int v) { for (int i = x; i <= len; i += lowbit(i)) c[i] += v; }
    ll query(int x) { ll ans = 0; for (int i = x; i; i -= lowbit(i)) ans += c[i]; return ans; }
}bit;
int main()
{
    int n; read(n); bit.len = n; ll rev = 0, ans = 1e18;
    for (int i = 1; i <= n; ++i)
    {
        read(p[i]); rev += bit.query(bit.len) - bit.query(p[i]);
        bit.add(p[i], 1); pos[p[i]] = i;
    }
    ans = std::min(ans, rev);
    for (int i = 1; i < n; ++i) rev += 1 - pos[i] + n - pos[i], ans = std::min(ans, rev);
    printf("%lld\n", ans); return 0;
}