解题报告

题意：

求逆序数。

思路：

线段树离散化处理。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define LL long long using namespace std; LL sum[2001000],num[501000],_hash[501000]; void push_up(int rt) { sum[rt]=sum[rt*2]+sum[rt*2+1]; } void update(int rt,int l,int r,int p,LL v) { if(l==r) { sum[rt]=+v; return; } int mid=(l+r)/2; if(p<=mid)update(rt*2,l,mid,p,v); else update(rt*2+1,mid+1,r,p,v); push_up(rt); } LL q_sum(int rt,int l,int r,int ql,int qr) { if(ql>r||qr
      
       
 Ultra-QuickSort 
       
 
        
 
         
 
          
Time Limit: 7000MS
 
          
 
 
          
Memory Limit: 65536K
 
         
 
         
 
          
Total Submissions: 41278
 
          
 
 
          
Accepted: 14952
 
         
 
        
 
       
 
       
 
       
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 sZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIuIEZvciB0aGUgaW5wdXQgc2VxdWVuY2UgPGJyPgo8Y2VudGVyPjkgMSAwIDUgNCAsPC9jZW50ZXI+Cjxicj4KVWx0cmEtUXVpY2tTb3J0IHByb2R1Y2VzIHRoZSBvdXRwdXQgPGJyPgo8Y2VudGVyPjAgMSA0IDUgOSAuPC9jZW50ZXI+Cjxicj4KWW91ciB0YXNrIGlzIHRvIGRldGVybWluZSBob3cgbWFueSBzd2FwIG9wZXJhdGlvbnMgVWx0cmEtUXVpY2tTb3J0IG5lZWRzIHRvIHBlcmZvcm0gaW4gb3JkZXIgdG8gc29ydCBhIGdpdmVuIGlucHV0IHNlcXVlbmNlLgo8cCBjbGFzcz0="pst">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
 Waterloo local 2005.02.05