NOIP 2013 洛谷P1966 火柴排队 (树状数组求逆序对)

2022-11-29,,,,

对于a[],b[]两个数组,我们应选取其中一个为基准,再运用树状数组求逆序对的方法就行了。

大佬博客:https://www.cnblogs.com/luckyblock/p/11482130.html

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,M=1e8-3;
struct node{
int val,num;
}a[N],b[N];
int c[N],lsh[N],n;
LL ans; bool cmp(node x,node y){
return x.val<y.val;
} int lowbit(int x){
return x&(-x);
} void ins(int x){
while(x<=n){
c[x]++;
x+=lowbit(x);
}
} LL que(int x){
LL sum=0;
while(x){
sum+=c[x];
x-=lowbit(x);
}
return sum;
} int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].num=i;
for(int i=1;i<=n;i++) scanf("%d",&b[i].val),b[i].num=i;//记录位置
sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++) lsh[a[i].num]=b[i].num;//离散化
for(int i=1;i<=n;i++){
ins(lsh[i]);
ans+=i-que(lsh[i]);
ans%=M;
}
cout<<ans;
}

NOIP 2013 洛谷P1966 火柴排队 (树状数组求逆序对)的相关教程结束。

《NOIP 2013 洛谷P1966 火柴排队 (树状数组求逆序对).doc》

下载本文的Word格式文档,以方便收藏与打印。