题意: 链接
方法: 线段树求逆序对+1~n逆序数性质
解析: 其实这篇题解的意义就是在写1~n逆序数的性质，按照题意先求出原数组的逆序对的个数，，然后开始考虑将第一个数移至最后一个的性质。因为数只有0~n-1,我们知道对于第一个数x[1]，比他小的数有x[1]个,比他大的数有n-1-x[1]个，如果把它移到最后一个，则减少了x[1]个逆序对,增加了n-1-x[1]个逆序对,所以逆序的变化应该是+=n-2*x[1]-1.
#include <stdio.h>#include <algorithm>#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define MAXN 5555 using namespace std ;int sum[MAXN<<2] ;void push_up(int rt){sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;}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 p , int l , int r , int rt){if(l == r){sum[rt] ++ ;return ;}int m = (l + r) >> 1 ;if(p <= m) update(p , lson) ;else update(p , rson) ;push_up(rt) ;}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 x[MAXN] ;int main(){int n ;while(~scanf("%d" , &n)){build(0 , n-1 , 1) ;int ret = 0 ;for(int i = 0 ; i < n ; i++){scanf("%d" , &x[i]) ;ret += query(x[i] , n-1 ,0 , n-1 , 1) ;update(x[i] , 0 , n-1 , 1) ;}int tot = ret;for(int i =0; i < n ; i ++){ret += n – x[i]- x[i]-1;tot = min(tot , ret);}printf("%d\n" , tot) ;}}
记忆的屏障，曾经心动的声音已渐渐远去。
