当先锋百科网

首页 1 2 3 4 5 6 7

nyoj117 求逆序数【线段树】

求逆序数

时间限制： 2000 ms  |  内存限制： 65535 KB
难度： 5
描述

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

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入
第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出
输出该数列的逆序数
样例输入 
2
2
1 1
3
1 3 2
样例输出 
0
1

来源

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define Max 1000010
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
long long sum[Max<<2];
struct Node{int t;int pos;
}A[Max];
bool cmp(Node a,Node b)
{if(a.t==b.t)return a.pos>b.pos;elsereturn a.t>b.t;
}
void buildtree(int l,int r,int rt)
{sum[rt]=0;if(l==r)return;int mid=(r+l)>>1;buildtree(lson);buildtree(rson);
}
int query(int ll,int rr,int l,int r,int rt)
{if(l==ll&&rr==r)return sum[rt];int mid=(l+r)>>1;if(mid>=rr)return query(ll,rr,lson);else if(ll>mid)return query(ll,rr,rson);else {return query(ll,mid,lson)+query(mid+1,rr,rson);}
}
void update(int rr,int l,int r,int rt)
{sum[rt]++;if(l==r)return ;int mid=(l+r)>>1;if(mid>=rr)update(rr,lson);else update(rr,rson);
} 
int main()
{int t,i,j,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;++i){scanf("%d",&A[i].t);A[i].pos=i+1;}buildtree(1,n,1);stable_sort(A,A+n,cmp);long long ans=0;for(i=0;i<n;++i){update(A[i].pos,1,n,1);if(A[i].pos==1)continue;ans+=query(1,A[i].pos-1,1,n,1);}printf("%lld\n",ans);}return 0;
}

树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define Max 1000005
using namespace std;
int c[Max];
struct Node{int t;int pos;
}A[Max];
int n;
bool cmp(Node a,Node b)
{if(a.t==b.t)return a.pos>b.pos;return a.t>b.t;
}
int low(int n)
{return n&(-n);
}
int sum(int t)
{int s=0;while(t>0){s+=c[t];t-=low(t);}return s;
}
void update(int t)
{while(t<n){c[t]+=1;t+=low(t);}
}
int main()
{int t,i,j;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;++i){scanf("%d",&A[i].t);A[i].pos=i+1;c[i]=0;}stable_sort(A,A+n,cmp);long long ans=0;for(i=0;i<n;++i){update(A[i].pos);if(A[i].pos==1)continue;ans+=sum(A[i].pos-1);}printf("%lld\n",ans);}return 0;	
}

归并排序 

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAX=1000010;
long long array[MAX];
long long temp[MAX];
long long count;
void Merge(int l,int mid,int r)
{int i=l;int j=mid+1;int k=l;while(i<=mid&&j<=r){if(array[i]>array[j]){temp[k++]=array[j++];count+=mid-i+1;}else {temp[k++]=array[i++];}}while(i<=mid)temp[k++]=array[i++];while(j<=r)temp[k++]=array[j++];for(i=l;i<=r;++i){array[i]=temp[i];}
}
void Merge_sort(int l,int r)
{if(l<r){int mid=(l+r)>>1;Merge_sort(l,mid);Merge_sort(mid+1,r);Merge(l,mid,r);}
}
int main()
{int t,i,j,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;++i){scanf("%lld",&array[i]);}count=0;Merge_sort(0,n-1);printf("%lld\n",count);}return 0;
}