树状数组求逆序对_N紫O色I

http://blog.sina.com.cn/u/5298772330

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

树状数组求逆序对

(2019-06-26 16:36:32)

分类：数据结构，指针

树状数组求逆序对，是其中的重要应用方式之一：

求逆序对

给定一个序列a1,a2,a3,……,an,如果存在iaj,那么我们称之为逆序对，求给定序列中逆序对的数目。

输入

第一行为n,表示序列的长度，接下来的n行，第i+1行表示序列的第i个数。

输出

所有逆序对的总数

样例输入

3 2 3 2

样例输出

一）直接树状数组，相当于桶排序，数组要开得很大，或者超限；

#include "bits/stdc++.h"

#define lowbit(x) (x&-x)

#define LL long long

using namespace std;

const int maxn = 1e6+10;

int t[maxn];

void add(int x){ while(x<=maxn) t[x]++, x+= lowbit(x);}

int query(int x)

{ int ans=0;

while(x) ans+=t[x],x-=lowbit(x);

return ans;

}

int main(){

int n;scanf("%d",&n);

LL ans=0;//此处应题目需要，ybt1311需要long long

for(int i=1;i<=n;i++)//A行

{ int t;scanf("%d",&t);

add(t);//B

ans +=1LL*(i-query(t));//C行

} printf("%lld\n",ans);

return 0;

}

单选题：A) C)

二）离散化处理，用序号开数组，数组可以比较小：

#include "bits/stdc++.h"

#define lowbit(x) (x&-x)

using namespace std;

const int maxn= 500005;

int c[maxn]; //树状数组

int n;

struct node

{

int v;

int order;//离散化记录

bool operator < (const node x) const{

if(v==x.v) return order < x.order;

return v < x.v;

}

} a[maxn];

void update(int t, int value){

for (int i = t; i <= n; i += lowbit(i)) c[i] += value;

}

int getsum(int t){

int sum = 0;

for (int i = t; i >= 1; i -= lowbit(i)) sum += c[i];

return sum;

}

int main(){

scanf("%d", &n);

for (int i = 1; i <= n; i++) //离散化

{

scanf("%d", &a[i].v);

a[i].order = i;//用序号构筑映射

}

sort(a + 1, a + n + 1);//从1到n排序

long long ans = 0;

for (int i = 1; i <= n; i++)

{

update(a[i].order, 1);

ans += i - getsum(a[i].order); //减去小于的数即为大于的数即为逆序数

}

printf("%lld\n", ans);

return 0;

}

单选：1)D 2)A

多选：1)B,C

三）Swaps and Inversions　HDU6318

Long long ago, there was an integer sequence a.

Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay x yuan for every inversion in the sequence.

You don't want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay y yuan to swap any two adjacent elements.

What is the minimum amount of money you need to spend?

The definition of inversion in this problem is pair (i,j) which 1≤iaj.

Input

There are multiple test cases, please read till the end of input file.

For each test, in the first line, three integers, n,x,y, n represents the length of the sequence.

In the second line, n integers separated by spaces, representing the orginal sequence a.1≤n,x,y≤100000, numbers in the sequence are in [?109,109]. There're 10 test cases.

Output

For every test case, a single integer representing minimum money to pay.

Sample Input

3 233 666

1 2 3

3 1 666

3 2 1

Sample Output

题目意思：

给你一个长度为n的数列

开始检查，如果某两个数不是从小大大顺序的，有一个就罚x元，

或者也可以直接在检查之前对不符合要求的调换位置（相邻的）

花费y元

然后要你求最小的花费

所以就是直接求这个序列的逆序数然后乘以x和y花费中较小的一个

逆序数可以归并或者数状数组求解

参考程序一，使用归并排序：

#define max_v 100005

using namespace std;

typedef long long LL;

LL a[max_v];

LL temp[max_v];

LL ans;

void mer(int s,int m,int t)

{

int i=s;

int j=m+1;

int k=s;

while(i<=m && j<=t)

{

if(a[i] <= a[j]) temp[k++]=a[i++];

else

{

ans+=j-k;//求逆序数

temp[k++]=a[j++];

}

while(i <= m) temp[k++]=a[i++];

while(j <= t) temp[k++]=a[j++];

}

void megsort(int s,int t)

{

if(s < t)

{

int m=(s+t)/2;

megsort(s,m);

megsort(m+1,t);

mer(s,m,t);

for(int i=s;i<=t;i++) a[i]=temp[i];

}

int main()

{

int n;

LL c1,c2;

while(~scanf("%d %lld %lld",&n,&c1,&c2))

{

if(n==0) break;

ans=0;

for(int i=0;i

megsort(0,n-1);

printf("%lld\n",ans*min(c1,c2));

}

return 0;

}

参考程序二，树状数组：

#include

using namespace std;

#define max_v 500005

int n;

struct node

{

int v;

int pos;

} p[max_v];

int c[max_v];

int re[max_v];

int maxx;

int lowbit(int x)

{

return x&(-x);

}

void update(int x,int d)

{

while(x < max_v)

{

c[x]+=d;

x+=lowbit(x);

}

int getsum(int x)//返回1到x中小与等于x的数量

{

int res=0;

while(x > 0)

{

res+=c[x];

x-=lowbit(x);

}

return res;

}

bool cmp(node a,node b)

{

if(a.v!=b.v) return a.v < b.v;

else return a.pos < b.pos;

}

int main()

{

long long c1,c2;

while(~scanf("%d %lld %lld",&n,&c1,&c2))

{

if(n==0) break;

memset(c,0,sizeof(c));

for(int i=1;i<=n;i++)

{

scanf("%d",&p[i].v);

p[i].pos=i;

}

sort(p+1,p+1+n,cmp);

long long ans=0;

for(int i=1;i<=n;i++)

{

ans+=(i-getsum(p[i].pos)-1);//先找再更新，避免getsum的时候算上自己

update(p[i].pos,1);

}

printf("%lld\n",ans*min(c1,c2));

}

return 0;

}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：树状数组：第k个数

后一篇：道路铺设--货币系统--赛道建设

新浪BLOG意见反馈留言板　欢迎批评指正