欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-21 21:37:26
此题有两种建树方式! Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers ......

此题有两种建树方式!

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

题目大意:

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

逆序的定义

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

核心思想:

我们用结构体来存储排列:
POJ 2299-Ultra-QuickSort-线段树的两种建树方式
a[i].x表示第i个数的数值,a[i].id表示第i个数的位置。

对于每一个数a[i].x,我们找到位置在它前面并且数值比它大的数的个数c[i],c数组的和就是答案。
线段树
我们在统计个数的时候,数要满足两个条件:
1、位置在它前面
2、数值比它大

我们在空间时间上分别加以控制来满足这两个条件。
空间:线段树的左右区间
时间:线段树的更新顺序
所以此题有两种建树方式

方式一

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

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

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

方式二

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

注意:此题目数的数值范围是1e10,将数值作为线段树区间长度开不出这么大的数组。解决方法是离散化
POJ 2299-Ultra-QuickSort-线段树的两种建树方式
离散前后的映射函数是:
POJ 2299-Ultra-QuickSort-线段树的两种建树方式

离散后的数值范围是不同数值的个数,也就是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;
}