- #include <stdio.h>
- int f[100005];
- int g[100005];
- long long ans;
- void Sort(int x, int y)
- {
- if(x >= y)
- return ;
- int mid = (x+y)>>1;
- Sort(x, mid);
- Sort(mid+1, y);
- int i = x;
- int j = mid+1;
- int k = x;
- while(i<=mid || j<=y)
- {
- if(i>mid)
- {
- g[k++] = f[j++];
- }
- else if(j>y)
- {
- g[k++] = f[i++];
- }
- else if(f[i]<=f[j])
- {
- g[k++] = f[i++];
- }
- else if(f[i]>f[j])
- {
- ans += mid - i + 1;
- g[k++] = f[j++];
- }
- }
- for(k=x; k<=y; ++k)
- f[k] = g[k];
- }
- int main(void)
- {
- int n;
- while(scanf("%d", &n) == 1)
- {
- for(int i=0; i<n; ++i)
- scanf("%d", &f[i]);
- ans = 0;
- Sort(0, n-1);
- printf("%lld\\n", ans);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/050720134464.html
来源: http://www.codesnippet.cn/detail/050720134464.html