树状数组求逆序对

废话不多说,直接上代码。

#include <cstdio>
#include <algorithm>
#define MAXN 1000
using namespace std;

struct node {
 int val;
 int index;
}nodes[MAXN];//输入数组 

int n;//总数列长度 
int a[MAXN];//离散化数组 
int c[MAXN];//树状数组 
int ans;//答案 

int cmp(const node a,const node b) {
 if(a.val<b.val)
 return true;
 else 
 return false;
} 

int lowbit(int x) {
 return x&amp;(-x);
}

void update(int pos,int data) {
 for(int i=pos;i<=n;i+=lowbit(i))
 c[i] += data;
}

int sum(int x) {
 int an = 0;
 for(int i=x;i>=1;i-=lowbit(i))
 an += c[i];
 
 return an;
}

int main() {
 scanf("%d",&amp;n);
 for(int temp,i=1;i<=n;i++) {
 scanf("%d",&amp;temp);
 nodes[i].index = i;
 nodes[i].val = temp;
 }
 
 sort(nodes+1,nodes+1+n,cmp);
 
 for(int i=1;i<=n;i++) //离散化
 a[nodes[i].index] = i;//在这里只关心数值的大小顺序而不是大小本身 
 
 for(int i=1;i<=n;i++) { 
 update(a[i],1); 
 ans += i - sum(a[i]);//之前比a[i]大的数 
 } 
 
 printf("%d",ans);
 
 return 0;
}

顺便用离散化优化了一下。

这里的i一定要从1开始,如果为0的话lowbit()就无法使用了。

Last modification:March 3rd, 2019 at 01:16 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment