树状数组—求逆序数的个数

115 阅读 0 评论 76 点赞

我是靠谱客的博主优雅秀发，最近开发中收集的这篇文章主要介绍树状数组—求逆序数的个数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem 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

大体的题意：

给你n个数，让你求一求有几个逆序数。

思路：

逆序数，换句话说就是让我求一求数的左边有几个比它大的数字。

在这里我们用到了离散化。

#if 0
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
using namespace std;
const int MAXN=500000+50; 
int n; 
int b[MAXN];
int c[MAXN];

struct node
{
 int v,id;
 
 bool operator <(const node & a)const
 {
  return v<a.v; 
 }
   
}a[MAXN];
int lowbit(int x)
{
 return x&(-x);
}
void add(int x,int v)
{
 for( ; x<=MAXN ; x+=lowbit(x))
 {
  c[x]+=v;
 }
}
int sum(int x)
{
 int sum=0;
 for( ; x>0; x-=lowbit(x))
  sum+=c[x];
  
 return sum; 
}
int main()
{
 while(cin>>n&&n)
 {
  memset(c,0,sizeof(c));
  memset(b,0,sizeof(b));
  memset(a,0,sizeof(a));
  
  for(int i=1; i<=n; i++) 
  {
   scanf("%d",&a[i].v);
   a[i].id=i;
  }
  
  sort(a+1,a+n+1);
  b[a[1].id]=1;               //离散化
  for(int i=2; i<=n; i++)
  {
   if(a[i].v==a[i-1].v)
    b[a[i].id]=b[a[i-1].id];
   else
    b[a[i].id]=i; 
  }
  
  long long int s=0;
  for(int i=1; i<=n; i++)
  {
   
   int temp=i-1-sum(b[i]);// int temp=sum(n)-sum(b[i]);
   
   add(b[i],1);
   s+=temp;
  }
 
  
  cout<<s<<endl;
 }
  
 
}
#endif