大意:求一个序列的逆序数对数,然后把前i个元素移动到尾部去,然后求这些序列中最小的逆序数对数。
思路:利用时效性来求逆序数对数,可以达到O(nlogn)的时间复杂度。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int maxn = 5100; int sum[maxn<<2]; int x[maxn]; int n; int ql, qr; int p, v; void pushup(int o) { sum[o] = sum[o*2] + sum[o*2+1]; } void build(int o, int L, int R) { int M = L + (R-L)/2; sum[o] = 0; if(L == R) ; else { build(o*2, L, M); build(o*2+1, M+1, R); pushup(o); } } int query(int o, int L, int R) { int M = L + (R-L)/2, ans = 0; if(ql <= L && R <= qr) return sum[o]; if(ql <= M) ans += query(o*2, L, M); if(M < qr) ans += query(o*2+1, M+1, R); return ans; } void update(int o, int L, int R) { int M = L + (R-L)/2; if(L == R) sum[o] += v; else { if(p <= M) update(o*2, L, M); else update(o*2+1, M+1, R); pushup(o); } } void read_case() { build(1, 0, n-1); } void solve() { read_case(); int sum = 0; for(int i = 0; i < n; i++) { scanf("%d", &x[i]); p = x[i], v = 1; ql = x[i], qr = n-1; sum += query(1, 0, n-1); update(1, 0, n-1); } int ans = sum; for(int i = 0; i < n; i++) { sum += (n-1-x[i])-x[i]; ans = min(ans, sum); } printf("%d\n", ans); } int main() { while(~scanf("%d", &n)) { solve(); } return 0; }