首页 > 代码库 > 数状数组求逆序对

数状数组求逆序对

逆序对在很多地方用的到。以前都是用归并排序或线段树求,在《mato的文件管理》看到有人用树状数组求,很简单!整理如下:

思路:

       首先,开一个大小为这些数的最大值的数组,作为树状数组。

       然后,将各个数按顺序依次加入该数组。方法为:这个数大小对应的它在线段树中的位置,对这个位置上的数加1,并更新树状数组。所以当前树状数组中存着所有原数字序列中当前数前面的数,而getsum(i)就是 i 前面小于等于 i 的数的个数。i-getsum(i)-1也就是大于它的个数。这就是逆序对了。

  把每一个的逆序对数加起来就是答案了。

问题:

  数值太大。

  离散化。树状数组内不存数本身而是存它的排序。

 

代码:

技术分享
 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn=1e6+7;
 5 int n;
 6 int sz[maxn],c[maxn];
 7 struct node
 8 {
 9     int dat,pos;
10 }nd[maxn];
11 
12 bool cmp(node a,node b)
13 {
14     return a.dat<b.dat;
15 }
16 inline int lowbit(int x)
17 {
18     return x&(-x);
19 }
20 int getsum(int x)
21 {
22     int sum=0;
23     for(;x>0;x-=lowbit(x))sum+=c[x];
24     return sum;
25 }
26 void updat(int x)
27 {
28     for(;x<=n;x+=lowbit(x))c[x]++;
29 }
30 int main()
31 {
32     cin>>n;
33     for(int i=1;i<=n;i++)
34     {
35         scanf("%d",sz+i);
36         nd[i].dat=sz[i];nd[i].pos=i;
37     }
38     sort(nd+1,nd+1+n,cmp);
39     int js=1;
40     sz[nd[1].pos]=1;
41     for(int i=2;i<=n;i++)
42     {
43         if(nd[i].dat==nd[i-1].dat)sz[nd[i].pos]=js;
44         else sz[nd[i].pos]=++js;
45     }
46     long long ans=0;
47     for(int i=1;i<=n;i++)
48     {
49         ans+=i-getsum(sz[i])-1;//<=sz[i]
50         updat(sz[i]);
51     }
52     cout<<ans;
53     return 0;
54 }
View Code

 

数状数组求逆序对