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

2019-08-16 07:59:36来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

原文链接:https://www.cnblogs.com/NothingbutFight/p/11306760.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Reliable Multicast Programming(PGM)协议

下一篇:选择排序的理解