树状数组求逆序对
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 1 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
一个板子题:
代码如下:
#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);
}
}
上一篇: numpy知识点补充