欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组求逆序对

程序员文章站 2022-05-10 15:33:24
...

step1 离散化

当数字范围很大的时候需要离散化,比如:2333333 9999999999 1

我萌也开不了那么大的数组呀,所以我们进行离散化:

(1)排序:1 2333333 9999999999

(2)重新分配值:1 2 3

具体代码:

for(int i=1;i<=n;i++){
    scanf("%d",&p[i].val);
    p[i].pos=i;
}
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++){
    a[p[i].pos]=i;
}

比如:9 1 0 5 4

位置:1 2 3 4 5

for(int i=1;i<=n;i++){//p[1]到p[n]的val递增,把其相应的位置设为1-n
    a[p[i].pos]=i;
}

a[i]:=第i个元素离散化后的结果。

val:9 1 0 5 4

a:   5 2 1 4 3

step2 求逆序对

ll ans=0;
for(int i=1;i<=n;i++){
    add(a[i]);
    ans+=i-sum(a[i]);
}

每次加一个元素a[i],此时加了i个元素,i-1个元素的位置都在a[i]之前,

然后求sum(a[i]),求出了位置在a[i]之前的,值小于a[i]的元素个数(包括a[i]本身),那么已经插入了i个元素,i-sum(a[i])

就是值大于a[i]的元素的个数

比如:5 2 1 4 3这个例子,蓝色是当前插入的元素黄色是它对应的逆序对

(1)插5

0 0 0 0 1      1-sum(5)=0       5    新增0个逆序对

(2)插2

0 1 0 0 1      2-sum(2)=1       5 2   新增1个逆序对,5,2

(3)插1

1 1 0 0     3-sum(1)=2       5 2 1  新增2个逆序对,5,1;2,1

(4)插4

1 1 0 1 1      4-sum(4)=1       5 2 1 4  新增1个逆序对,5,4

(5)插3

1 1 1 1 1      5-sum(3)=2       5 2 1 4 3  新增2个逆序对,5,3;4,3

一个板子题:

poj2299

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const int N=500010;

struct A{
    int val,pos;
}p[N];
int a[N],c[N];

bool cmp(A a,A b){
    return a.val<b.val;
}

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

void add(int x){
    for(int i=x;i<=N;i+=lowbit(i)){
        c[i]++;
    }
}

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

int main(){
    int n;
    while(scanf("%d",&n)&&n){
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            scanf("%d",&p[i].val);
            p[i].pos=i;
        }
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++){
            a[p[i].pos]=i;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            add(a[i]);
            ans+=i-sum(a[i]);
        }
        printf("%lld\n",ans);
    }
}