1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int n, a[500005], b[500005]; ll ans; void init(){ for(int i = 0; i < n; ++i) a[i] = read(); } void Merge(int ls, int rs, int re){ int lp = ls, rp = rs, tp = ls; while(lp < rs && rp < re){ if(a[lp] <= a[rp]) b[tp++] = a[lp++]; else b[tp++] = a[rp++], ans += 1ll * (rs - lp); } while(lp < rs) b[tp++] = a[lp++]; while(rp < re) b[tp++] = a[rp++]; memcpy(a + ls, b + ls, sizeof(int) * (re - ls)); } void ms(int l, int r){ int len = r - l, mid = (r + l) >> 1; if(len == 1) return ; ms(l, mid), ms(mid, r); Merge(l, mid, r); } void solve(){ ans = 0; ms(0, n); printf("%lldn", ans); } int main(){ while(n = read()){ init(); solve(); } return 0; }
|
近期评论