P2995 [USACO10NOV]Cow Photographs G 题解

· · 题解

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;
}