大意：n次操作原串查询逆序数，求出所有串中最小的逆序数。
求逆序数属于线段树的统计问题，建立空树，每次进行插点时进行一次query操作即可。n次操作可以套用结论：如果是0到n的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少a[i],而增加n-1-a[i]。
#include <iostream>
#include <cstdio>
using namespace std; const int maxn = 5e3 + ;
int sumv[maxn << ]; void PushUp (int rt) {
sumv[rt] = sumv[rt * ] + sumv[rt * +];
} void build (int l, int r, int rt) {
sumv[rt] = ;
if (l == r) {
return ;
}
int m = (l + r) / ;
build (l, m, rt * );
build (m + , r, rt * + );
} void update (int p, int l, int r, int rt) {
if (l == r) {
sumv[rt] ++;
return ;
}
int m = (l + r) / ;
if (p <= m) {
update (p, l, m, rt * );
}
if (p > m) {
update (p, m + , r, rt * + );
}
PushUp (rt);
} int query (int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sumv[rt];
}
int m = (l + r) / ;
int ret = ;
if (L <= m) {
ret += query (L, R, l, m, rt * );
}
if (R > m) {
ret += query (L, R, m + , r, rt * + );
}
return ret;
} int x[maxn]; int main () {
int n;
while (~scanf ("%d", &n)) {
build (, n - , );
int sum = ;
for (int i = ; i < n; ++ i) {
scanf ("%d", &x[i]);
sum += query (x[i], n - , , n - , );
update (x[i], , n - , );
}
int res = sum;
for (int i = ; i < n; ++ i) {
sum = sum + n - x[i] - - x[i];
res = min (res, sum);
}
printf ("%d\n", res);
}
return ;
}