HDU 2689 Sort IT [tree array] [data structure]

Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=2689
——————————— —————————————————-.
Sort it

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4140 Accepted Submission(s): 2945

Problem Description
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation: swap 5 and 4.

Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

Output
For each case, output the minimum times need to sort it in ascending order on a single line.

Sample Input
3
1 2 3
4
4 3 2 1

Sample Output
0
6< /p>

Author
WhereIsHeroFrom

Source
ZJFC 2009-3 Programming Contest

——————————————— —————————————-.

The main idea of ​​the topic:
It is to ask how many times the sequence needs to be exchanged for bubble sorting

The idea of ​​solving the problem :
After clarifying the meaning of the title, it is very easy to understand.
For each number, how many times are exchanged, that is, before this number appears, there are several numbers larger than it. Just add up.

Here we maintain a tree-like array, and each time the value of a[i] is updated to 1, then the sum of 1~a[i] when querying is the number larger than it before it appears. The number of.

Not difficult to deal with.

Attach this question code
———————————-.

#include #define abs(x) (((x)>0)?(x):-(x))< span class="hljs-preprocessor">#define lalal puts("*********")using namespace std;/************* *************************/const int N = 1000+5;#define lowbit(x) (x&-x)int cnt,sum[N],a[N];void update(int index,int val){ for(int i=index;i<=cnt;i+=lowbit(i)) sum[i]+ =val; return ;}int getSum(int index ){ int ans = 0; for (int i=index;i>0;i-=lowbit(i)) ans+=sum[ i]; return ans;}int main(){  while(~scanf("%d",&cnt)){ memset(sum,0,sizeof(sum)); for(int i=1;i <=cnt;i++) scanf("%d",&a[i]); int ans=0; for(int i=cnt;i;i--){ ans+=getSum(a[i]); update(a[i],1 );} printf("%d
",ans);} return 0;}