POJ 2299-Ultra-QuickSort-线段树的两种建树方式

此题有两种建树方式！

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

5
9
1
0
5
4
3
1
2
3
0

sample output

6
0

题目大意：

给定一个排列，求这个排列的逆序数。

逆序的定义

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。

核心思想：

我们用结构体来存储排列：

a[i].x表示第i个数的数值，a[i].id表示第i个数的位置。

对于每一个数a[i].x，我们找到位置在它前面并且数值比它大的数的个数c[i]，c数组的和就是答案。
线段树。
我们在统计个数的时候，数要满足两个条件：
1、位置在它前面
2、数值比它大
我们在空间和时间上分别加以控制来满足这两个条件。
空间：线段树的左右区间。
时间：线段树的更新顺序。
所以此题有两种建树方式，

方式一

从空间上加以控制来满足位置在它前面的条件；
从时间上加以控制来满足数值比它大的条件。

线段树的左右区间表示原排列中数的位置，通过控制查询时左右区间的端点来满足位置在它前面的条件。
我们将a数组按x降序排列，按照新的顺序依次更新线段树，数值的大的先进入（更新）线段树，所以现在从线段树上查询到的个数一定满足数值比它大的条件。

此方式建树不需要离散化，下面的方式需要离散化。

方式二

从空间上加以控制来满足数值比它大的条件；
从时间上加以控制来满足位置在它前面的条件。
线段树的左右区间表示原排列中数的数值，通过控制查询时左右区间的端点来满足数值比它大的条件。
我们将a数组按id升序排列（也就是原顺序），位置靠前的先进入（更新）线段树，所以现在从线段树上查询到的个数一定满足位置在它前面的条件。

注意：此题目数的数值范围是1e10，将数值作为线段树区间长度开不出这么大的数组。解决方法是离散化。

离散前后的映射函数是：

离散后的数值范围是不同数值的个数，也就是5e5。这样就可以开数组建树了。

方式一代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int n=5e5+20;
char s[20];
//存原排列 
struct node{
    int x,id;
}a[n];
struct tnode{
    int l,r,sum;
}tr[n<<2];
void pushup(int m)
{
    tr[m].sum=tr[m<<1].sum+tr[m<<1|1].sum;
    return;
}
void build(int m,int l,int r)
{
    tr[m].l=l;
    tr[m].r=r;
    if(l==r)
    {
        tr[m].sum=0;
        return;
    }
    int mid=(l+r)>>1;
    build(m<<1,l,mid);
    build(m<<1|1,mid+1,r);
    pushup(m);
    return;
}
void update(int m,int x)
{
    if(tr[m].l==x&&tr[m].r==x)
    {
        tr[m].sum=1;
        return;
    }
    int mid=(tr[m].l+tr[m].r)>>1;
    if(x<=mid)
        update(m<<1,x);
    else
        update(m<<1|1,x);
    pushup(m);
    return;
}
int query(int m,int l,int r)
{
    if(tr[m].l==l&&tr[m].r==r)
        return tr[m].sum;
    int mid=(tr[m].l+tr[m].r)>>1;
    if(r<=mid)
        return query(m<<1,l,r);
    if(l>mid)
        return query(m<<1|1,l,r);
    return query(m<<1,l,mid)+query(m<<1|1,mid+1,r);
}
bool cmp(node p,node q)
{
    return p.x>q.x;
}
int main()
{
    int n;
    while(1)
    {
        scanf("%d",&n);
        if(!n)
            break;
        //根据n直接建树 
        build(1,1,n);
        //输入
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].id=i;
        }
        //排序，x大的先进入线段树 
        sort(a+1,a+n+1,cmp);
        //边更新边查询 
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=query(1,1,a[i].id);
            update(1,a[i].id);
        }
        //输出 
        printf("%lld\n",ans);
    }
    return 0;
}

方式二代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int n=5e5+20;
int b[n],cnt;
//存原排列 
struct node{
    int x,id;
}a[n];
struct tnode{
    int l,r,sum;
}tr[n<<2];
void pushup(int m)
{
    tr[m].sum=tr[m<<1].sum+tr[m<<1|1].sum;
    return;
}
void build(int m,int l,int r)
{
    tr[m].l=l;
    tr[m].r=r;
    if(l==r)
    {
        tr[m].sum=0;
        return;
    }
    int mid=(l+r)>>1;
    build(m<<1,l,mid);
    build(m<<1|1,mid+1,r);
    pushup(m);
    return;
}
void update(int m,int x)
{
    if(tr[m].l==x&&tr[m].r==x)
    {
        tr[m].sum=1;
        return;
    }
    int mid=(tr[m].l+tr[m].r)>>1;
    if(x<=mid)
        update(m<<1,x);
    else
        update(m<<1|1,x);
    pushup(m);
    return;
}
int query(int m,int l,int r)
{
    if(tr[m].l==l&&tr[m].r==r)
        return tr[m].sum;
    int mid=(tr[m].l+tr[m].r)>>1;
    if(r<=mid)
        return query(m<<1,l,r);
    if(l>mid)
        return query(m<<1|1,l,r);
    return query(m<<1,l,mid)+query(m<<1|1,mid+1,r);
}
bool cmp1(node p,node q)
{
    return p.x<q.x;
}
bool cmp2(node p,node q)
{
    return p.id<q.id;
}
int getid(int x)
{
    return lower_bound(b,b+cnt,x)-b+1;
}
int main()
{
    int n;
    while(1)
    {
        scanf("%d",&n);
        if(!n)
            break;
        //输入 
        a[0].x=-1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].id=i;
        }
        //先离散化 
        sort(a+1,a+n+1,cmp1);
        cnt=0;
        for(int i=1;i<=n;i++)
            if(a[i].x!=a[i-1].x)
                b[cnt++]=a[i].x;
        //根据离散后的cnt建树 
        build(1,1,cnt);
        //别忘了把a数组sort回来 
        sort(a+1,a+n+1,cmp2);
        //边更新边查询 
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int t=getid(a[i].x);
            ans+=query(1,t,n);
            update(1,t);
        }
        //输出 
        printf("%lld\n",ans);
    }
    return 0;
}