POJ训练计划2299_Ultra-QuickSort(线段树/单点更新)

解题报告

题意：

求逆序数。

思路：

线段树离散化处理。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#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<l)return 0;
    if(ql<=l&&r<=qr)return sum[rt];
    int mid=(l+r)/2;
    return q_sum(rt*2,l,mid,ql,qr)+q_sum(rt*2+1,mid+1,r,ql,qr);
}
int main()
{
    int n,i,j;
    while(~scanf("%d",&n))
    {
        LL ans=0;
        if(!n)break;
        memset(_hash,0,sizeof(_hash));
        memset(num,0,sizeof(num));
        memset(sum,0,sizeof(sum));
        for(i=0; i<n; i++)
        {
            scanf("%LLd",&num[i]);
            _hash[i]=num[i];
        }
        sort(_hash,_hash+n);
        int m=unique(_hash,_hash+n)-_hash;
        for(i=0; i<n; i++)
        {
            int t=lower_bound(_hash,_hash+m,num[i])-_hash+1;
            ans+=q_sum(1,1,m,t+1,m);
            update(1,1,m,t,1);
        }
        printf("%lld
",ans);
    }
    return 0;
}

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 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

Sample Output

6
0

Source

Waterloo local 2005.02.05