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
          
           #define lson root<<1#define rson root<<1|1#define hi puts("hi!");using namespace std;struct node{ int kd,val;}a[500005];int n,m,cnt[500050];long long tr[2000050];bool cmp(node a,node b){ return a.val
           
            >1; build(lson,l,mid); build(rson,mid+1,r); push_up(root);}void add(int root,int l,int r,int x,int p){ if(l==r) { tr[root]=1; return; } int mid=(l+r)>>1; if(p<=mid) { add(lson,l,mid,x,p); } if(p>mid) { add(rson,mid+1,r,x,p); } push_up(root);}long long query(int root,int l,int r,int x,int y){ long long ans=0; if(x<=l&&y>=r) { return tr[root]; } int mid=(l+r)>>1; if(x<=mid) { ans+=query(lson,l,mid,x,y); } if(y>mid) { ans+=query(rson,mid+1,r,x,y); } return ans;}int main(){ while(scanf("%d",&n)==1&&n) { long long ans1=0; memset(tr,0,sizeof(tr)); build(1,1,n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].kd=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { cnt[a[i].kd]=i; } for(int i=n;i>=1;i--) { ans1+=query(1,1,n,1,cnt[i]); add(1,1,n,1,cnt[i]); } printf("%lld\n",ans1); }}