题目链接
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Ultra-QuickSort produces the output
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The
input contains several test cases. Every test case begins with a line
that contains a single integer n < 500,000 -- the length of the input
sequence. Each of the the following n lines contains a single integer 0
≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is
terminated by a sequence of length n = 0. This sequence must not be
processed.
Output
For
every input sequence, your program prints a single line containing an
integer number op, the minimum number of swap operations necessary to
sort the given input sequence.
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
题目a[i]范围9e9+9,emmm,似乎会爆空间,似乎写过类似题,似乎必须离散化,似乎就这么写了。。。。。。
然后用树状数组解题并解出逆序数就...巴拉巴拉
/************************************************ ┆ ┏┓ ┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃ ┃ ┆ ┆┃ ━ ┃ ┆ ┆┃ ┳┛ ┗┳ ┃ ┆ ┆┃ ┃ ┆ ┆┃ ┻ ┃ ┆ ┆┗━┓ ┏━┛ ┆ ┆ ┃ ┃ ┆ ┆ ┃ ┗━━━┓ ┆ ┆ ┃ AC代马 ┣┓┆ ┆ ┃ ┏┛┆ ┆ ┗┓┓┏━┳┓┏┛ ┆ ┆ ┃┫┫ ┃┫┫ ┆ ┆ ┗┻┛ ┗┻┛ ┆ ************************************************ */ //#include<bits/stdc++.h> #include <stdio.h> #include <stdlib.h> #include <cmath> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <string> #include <ctype.h> #include <map> #include <vector> #include <set> using namespace std; const int maxn=5e5+10; int Tree[maxn],b[maxn]; struct node { int val,pos; }a[maxn]; bool cmp(node x,node y) { return x.val<y.val; } inline int lowbit(int x) //计算2^k { return (x&-x); } void add(int x,int value) { for(int i=x; i<maxn; i+=lowbit(i)) Tree[i]+=value; } int get(int x) { int sum=0; for(int i=x; i>0; i-=lowbit(i)) sum+=Tree[i]; return sum; } int main() { int n; while(~scanf("%d",&n)&&n) { memset(Tree,0,sizeof(Tree)); for(int i=1;i<=n;i++) { scanf("%d",&a[i].val);; a[i].pos=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) b[a[i].pos]=i; long long ans=0; for(int i=1;i<=n;i++) { add(b[i],1); ans+=i-get(b[i]); } printf("%I64d ",ans); } return 0; }