树状数组求解逆序数

树状数组求解逆序数

数列的逆序数可以使用归并排序求解，亦可以使用树状数组解决。现在献上两题，用树状数组求解逆序数。 POj 2299 Ultra-QuickSort ​​​http://poj.org/problem?id=2299​​​ 大意：一个排列经过多少次交换能够成为排好序的结果。 分析：之前用归并排序做过​​ 这次练习数据结构。离散（映射）+树状数组 例如：1 9 8 4 5 --->  1 5 4 2 3 依据数值的大小重新确定值，节省空间。 接着就是插入确定逆序： _ _ _ _ _ 1 _ _ _ _    (1~0) 1 _ _ _ 1    (5~3) 1 _ _ 1 1    (4~2) 1 1 _ 1 1    (2~0) 1 1 1 1 1    (3~0) 统计数字前面的空格总和——逆序 最后相加即可。

#include #include #include #include using namespace std;const int N=5e5+10;typedef long long LL;int d[N]; // disperse arrayLL c[N]; struct node{ int u,order;}a[N];int cmp(node t1,node t2){ return t1.u0){ ans=ans+c[dex]; dex=dex-lowbit(dex); } return ans;}int main(){ //freopen("cin.txt","r",stdin); int t,len; while(~scanf("%d",&len)&&len){ for(int i=0;i

nyist 117 求逆序数

​​1 3 2 的逆序数就是1。

（数字可以相等）

#include #include #include #include using namespace std;const int N=1e6+10;typedef long long LL;int d[N]; // disperse arrayLL c[N]; struct node{ int u,order;}a[N];int cmp(node t1,node t2){ return (t1.u0){ ans=ans+c[dex]; dex=dex-lowbit(dex); } return ans;}int main(){ //freopen("cin.txt","r",stdin); int t,len; cin>>t; while(t--){ scanf("%d",&len); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。