POJ 2299 Ultra-QuickSort 模板 求逆序对

题目Ultra-QuickSort
我特地又学习了树状数组求逆序对。如果不会树状数组，现在赶快点击之。
我一看这个是求逆序对的裸题，先用归并排序水了一发。
归并排序求逆序对？戳这里

#include<cstdio>
using namespace std;
typedef long long ll;
const ll boss=5e5;
ll a[boss+10],tmp[boss+10],n,s;

void mergesort(ll l,ll r)
{
if (l==r) return;
ll mid=(l+r)/2,i=l,j=mid+1,p=l;
mergesort(l,mid),mergesort(mid+1,r);
for (;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);
for (;i<=mid;tmp[p++]=a[i++]);
for (;j<=r;tmp[p++]=a[j++]);
for (i=l;i<=r;i++) a[i]=tmp[i];
}

int main(){for (ll i;scanf("%lld",&n),n;mergesort(1,n),printf("%lld\n",s)) for (s=0,i=1;i<=n;i++) scanf("%lld",&a[i]);}

然后我优化了一波时间，把它刷到了172ms.

#include<cstdio>
#include<ctype.h>
#include<cstring>
#define ll long long
using namespace std;
int a[500010],tmp[500010],n;ll s;

inline int read()
{
int x=0;char c=getchar();
for (;!isdigit(c);c=getchar());
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x;
}

void mergesort(int l,int r)
{
if (l==r) return;
int mid=(l+r)/2,i=l,j=mid+1,p=l;
mergesort(l,mid),mergesort(mid+1,r);
for (;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);
for (;i<=mid;tmp[p++]=a[i++]);
for (;j<=r;tmp[p++]=a[j++]);
for (i=l;i<=r;i++) a[i]=tmp[i];
}

void write(ll s)
{
if (s>9) write(s/10);
putchar(s%10+'0'); 
}

int main()
{
for (int i;n=read(),n;mergesort(1,n),write(s),puts("")) for (s=0,i=1;i<=n;i++) a[i]=read();
}

我又刷了一遍长度，把它刷到393。

#include<cstdio>
int a[500010],tmp[500010],n,i;long long s;void f(int l,int r){if(l<r){int mid=(l+r)/2,i=l,j=mid+1,p=l;f(l,mid),f(mid+1,r);for(;i<=mid&&j<=r;a[i]>a[j]?tmp[p++]=a[j++],s+=mid-i+1:tmp[p++]=a[i++]);for(;i<=mid;tmp[p++]=a[i++]);for(;j<=r;tmp[p++]=a[j++]);for(i=l;i<=r;i++)a[i]=tmp[i];}}main(){for(;scanf("%d",&n),n;f(1,n),printf("%lld\n",s))for(s=0,i=1;i<=n;i++)scanf("%d",&a[i]);}

归并排序到此结束。接下来介绍树状数组求逆序对。

题解

假设数列的成员全部在1-n之间。我们不妨来研究一下在数列末尾插入一个数时逆序对数量的变化。研究一会儿你就知道了，逆序对增加的数目等于该数字之前比它大的数字个数。这个很好理解吧。那么利用树状数组就可以在logn时间内找到在它之前比它大的元素个数。

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
const ll boss=5e5;
ll n,a,c[boss+10],s;

inline ll get(ll x){ll sum=0;for (;x>0;x-=lowbit(x)) sum+=c[x];return sum;}
inline void add(ll x,ll y){for (;x<=n;x+=lowbit(x)) c[x]+=y;}

int main()
{
for (ll i;scanf("%lld",&n),n;printf("%lld\n",s))
  {
  memset(c,0,sizeof c);
  for (s=0,i=1;i<=n;i++) 
    {
    scanf("%lld",&a);
    add(a,1);//在a后面的比a大的数字(假设是b)前面的比b小的数字多1
    s+=a-get(a);//add函数是往后加的，所以get(a)是在它之前比它小的数字的个数。由于所有数字均不同，故a-get(a)即为比它大的数字的个数。
    }
  } 
}

可是本题的题目不是如此，它的数据范围在1-999999999之间.我们无法构建1e9的数组来存储我们想要的数字。由于数字最多只有500000个，而且本题的答案也与数字本身无关，只与数字之间的关系有关。故这里又有一个神奇的方法:离散化。
只要将所给的数组转化为一个逆序对与该数组相同并且由1-n组成的数组，就可以完工了.
我们将数组元素与编号放到一个结构体里，按照元素大小排序，此时编号所形成的数组就是我们想要的了。不妨证明一下。
假设所求数组是样例的9,1,0,5,4.我们编号为{9,1}{1,2}{0,3}{5,4}{4,5},按照value排序得{0,3}{1,2}{4,5}{5,4}{9,1},这样就产生了一个新数组3,2,5,4,1,与样例的逆序对数量6是一样的。这样这题就迎刃而解了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
const ll boss=5e5;
struct node{ll id,value;}nico[boss+10];
inline bool cmp(node a,node b){return a.value<b.value;}
ll n,a,c[boss+10],s;

inline ll get(ll x){ll sum=0;for (;x>0;x-=lowbit(x)) sum+=c[x];return sum;}
inline void add(ll x,ll y){for (;x<=n;x+=lowbit(x)) c[x]+=y;}

int main()
{
for (ll i;scanf("%lld",&n),n;printf("%lld\n",s),s=0)
  { 
  memset(c,0,sizeof c);
  for (i=1;i<=n;i++) scanf("%lld",&a),nico[i].id=i,nico[i].value=a;
  sort(nico+1,nico+n+1,cmp);
  for (i=1;i<=n;i++) add(nico[i].id,1),s+=nico[i].id-get(nico[i].id);
  }
}

我觉得在求逆序对上还是归并排序好用。