POJ-2299-Ultra-QuickSort（单点更新 + 区间查询+离散化）-白红宇

POJ-2299-Ultra-QuickSort（单点更新 + 区间查询+离散化）

阅读量：5008 次

发布时间：2019-06-12

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

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             const int maxn=5e5+5;typedef long long ll;using namespace std;struct node{ ll l,r; ll sum;}tree[maxn<<2];int a[maxn],sub[maxn],cnt;void pushup(int m){ tree[m].sum=(tree[m<<1].sum+tree[m<<1|1].sum);}//void pushdown(int m)//{// if(tree[m].lazy)// {// tree[m<<1].lazy=tree[m].lazy;// tree[m<<1|1].lazy=tree[m].lazy;// tree[m<<1].sum=tree[m].lazy*(tree[m<<1].r-tree[m<<1].l+1);// tree[m<<1|1].sum=tree[m].lazy*(tree[m<<1|1].r-tree[m<<1|1].l+1);// tree[m].lazy=0; // } // return ;//}void build(int m,int l,int r){ tree[m].l=l; tree[m].r=r; tree[m].sum=0; if(l==r) { tree[m].sum=0; return ; } int mid=(tree[m].l+tree[m].r)>>1; build(m<<1,l,mid); build(m<<1|1,mid+1,r); pushup(m); return ;}void update(int m,int index ,int val){ if(tree[m].l==index&&tree[m].l==tree[m].r) { tree[m].sum++; return ; } int mid=(tree[m].l+tree[m].r)>>1; if(index<=mid) { update(m<<1,index,val); } else { update(m<<1|1,index,val); } pushup(m); return ; }ll query(int m,int l,int r){ if(l>r) { return 0; } if(tree[m].l==l&&tree[m].r==r) { return tree[m].sum; } // pushdown(m); int mid=(tree[m].l+tree[m].r)>>1; if(r<=mid) { return query(m<<1,l,r); } else if(l>mid) { return query(m<<1|1,l,r); } else { return query(m<<1,l,mid)+query(m<<1|1,mid+1,r); }}int main(){ int n; while(cin>>n) { if(n==0) { break; } for(int i=0;i

转载于:https://www.cnblogs.com/Staceyacm/p/11298857.html

你可能感兴趣的文章