poj2299 Ultra-QuickSort-白红宇

poj2299 Ultra-QuickSort

阅读量：5046 次

发布时间：2019-06-12

本文共 1912 字，大约阅读时间需要 6 分钟。

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 43339		Accepted: 15798

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.

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

59105431230

Sample Output

60 自从高二以来好像只用线段树没有写过树状数组……随便拿个求逆序对的题练练手

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define LL long long#define inf 0x7ffffff#define pa pair
                
                 #define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct dat{ int a,rnk;}a[500010];int d[500010];int c[500010];bool operator <(const dat &a,const dat &b){return a.a
                 
                  =1;i--) { ans+=query(d[i]); change(d[i]); } printf("%lld\n",ans); }}

转载于:https://www.cnblogs.com/zhber/p/4138428.html

你可能感兴趣的文章