poj 2299 树状数组求逆序对数+离散化

时间：2021-11-03 06:22:26
Ultra-QuickSort
Time Limit: 7000MS   Memory Limit: 65536K
Total Submissions: 54883   Accepted: 20184

Description

poj 2299 树状数组求逆序对数+离散化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.

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

Source

 
题意：给你长度为n个不同的数，问最少需要交换多少次使得升序 只能交换相邻的两个 其实就是冒泡排序的过程
题解：直接模拟的话会超时 树状数组处理，n只有100000 但是0 ≤ a[i] ≤ 999,999,999
如果开树状数组的话 会炸 所以先离散化一下 只要记录数的相对大小就可以了。求每个数的逆序数对数然后求和输出    
逆序对：设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉A[j]，则(i,j)就称为A中的一个逆序对。
 
还有一种归并排序的写法 再补
 /******************************

 code by drizzle

 blog: www.cnblogs.com/hsd-/

 ^ ^    ^ ^

  O      O

 ******************************/

 //#include<bits/stdc++.h>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #define ll __int64

 #define PI acos(-1.0)

 #define mod 1000000007

 using namespace std;

 int n;

 struct node

 {

     int v;

     int pos;

 }N[];

 int a[];

 int tree[];

 bool cmp(struct node aa,struct node bb)

 {

     return aa.v<bb.v;

 }

 int lowbit(int t) {return t&(-t);}

 void add(int i,int v){

     for(;i<=n;i+=lowbit(i))

         tree[i]+=v;

 }

 int sum(int i){//sum 就是统计之前有多少个小于i的数

    int ans=;

    for(;i>;i-=lowbit(i))

     ans+=tree[i];

    return ans;

 }

 int main()

 {

     while(~scanf("%d",&n)){

         if(n==)

             break;

         for(int i=;i<=n;i++)

         {

             scanf("%d",&N[i].v);

             N[i].pos=i;

         }

         sort(N+,N++n,cmp);

         for(int i=;i<=n;i++)//离散化

             a[N[i].pos]=i;

         for(int i=;i<=n;i++)//初始化

             tree[i]=;

         ll ans=;

         for(int i=;i<=n;i++)

         {

               add(a[i],);//注意修改值为1

               ans+=(i-sum(a[i]));

         }

         printf("%I64d\n",ans);

     }

     return ;

 }

相关文章