循环同构序列题解

AisDaeun 2 2024-01-19

循环同构序列([USACO 2010 Nov G]Cow Photographs

考虑计算转换成标准序列​(1, 2, ..., n)的最小交换次数(即逆序对数),然后通过循环同构序列之间的关系​O(1)计算转换到所有循环同构序列的最小交换次数​S

下面考虑​A = ( 1, 2, ..., n)与B = ​(2, 3, ..., n, 1)的关系。设原序列为​O​O中$1$的位置为​p_1,则​O中的$1$到​x=1位置需要​(p_1 - 1)步,​O中的$1$到​x=n位置需要​(n - p_1)步,那么​S_{O \rightarrow B} = S_{O \rightarrow A} - (p_1 - 1) + (n - p_1)

#include <algorithm>
#include <cctype>
#include <cstdio>
typedef long long LL;
int read() {
  int x = 0;
  char ch = getchar();
  while (!std::isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x;
}
const int maxn = 1e5 + 10;
LL a[maxn];
int n, p[maxn];
void add(LL *s, int i, int val) {
  for (; i <= n; i += i & -i) s[i] += val;
}
LL query(LL *s, int i) {
  LL res = 0;
  for (; i >= 1; i -= i & -i) res += s[i];
  return res;
}
int main() {
  n = read();
  LL rev = 0;
  for (int i = 1; i <= n; i++) {
    int x = read();
    add(a, x, 1);
    rev += i - query(a, x);
    p[x] = i;
  }
  LL ans = rev;
  for (int i = 1; i < n; i++) {
    rev = rev - (p[i] - 1) + (n - p[i]);
    ans = std::min(ans, rev);
  }
  printf("%lld\n", ans);
}