线段树求逆序数，先求出初始数组的逆序数(n logn)，然后o(1)推出其他逆序数。因为输入为0--n-1，所以建树从0开始。
code:
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include < string> #include <iostream> #include <sstream> #include < set> #include <queue> #include <stack> #include <fstream> #include <iomanip> #include <bitset> #include <list> #include <ctime> using namespace std ; #define SET(arr, what) memset(arr, what, sizeof(arr)) #define FF(i, a) for(i=0; i<a; i++) #define SD(a) scanf("%d", &a) #define SSD(a, b) scanf("%d%d", &a, &b) #define SF(a) scanf("%lf", &a) #define SS(a) scanf("%s", a) #define SLD(a) scanf("%lld", &a) #define PF(a) printf("%d\n", a) #define PPF(a, b) printf("%d %d\n", a, b) #define SZ(arr) (int)a.size() #define SWAP(a,b) a=a xor b;b= a xor b;a=a xor b; #define read freopen("in.txt", "r", stdin) #define write freopen("out.txt", "w", stdout) #define MAX 1<<30 #define ESP 1e-5 #define lson l, m, rt<<1|1 #define rson m+1, r, (rt<<1)+2 template< class T> inline T sqr(T a){ return a*a;} template< class T> inline void AMin(T &a,T b){ if(a==- 1||a>b)a=b;} template< class T> inline void AMax(T &a,T b){ if(a<b)a=b;} template< class T> inline T Min(T a,T b){ return a>b?b:a;} template< class T> inline T Max(T a,T b){ return a>b?a:b;} const int maxn = 5010 ; int sum[maxn<< 2] ; int data[maxn] ; void build( int l, int r, int rt){ sum[rt] = 0 ; if(l==r) return ; int m = (l + r) >> 1 ; build(lson) ; build(rson) ; } void update( int x, int l, int r, int rt){ sum[rt] ++ ; if(l==r) return ; int m = (l + r) >> 1 ; if(x<=m) update(x, lson) ; else update(x, rson) ; } int query( int L, int R, int l, int r, int rt){ if(L<=l&&r<=R) return sum[rt] ; int m = (l + r) >> 1 ; int ret = 0 ; if(L<=m) ret += query(L, R, lson) ; if(R>m) ret += query(L, R, rson) ; return ret ; } int main(){ int n, i, j, ini, ans ; while(~SD(n)){ build( 0, n- 1, 0) ; ini = 0 ; FF(i, n){ SD(data[i]) ; ini += query(data[i], n, 0, n- 1, 0) ; update(data[i], 0, n- 1, 0) ; } ans = ini ; FF(i, n){ ini += n - data[i] - data[i] - 1 ; ans = Min(ini, ans) ; } PF(ans) ; } return 0 ; }