求逆序对有两种方法:归并排序和树状数组,但是归并排序求得的逆序对是总共的逆序对数量,有些时候我们需要求得某个数后面的逆序对数量或者某个数前面的逆序对数量。
这种时候,则需要对归并排序进行扩展,非常的麻烦。这个时候我们就需要使用树状数组来求逆序对,使用树状数组的优势在于码量少,容易调试。但是如果值域大的话,需要进行离散化。
树状数组求逆序对的核心代码如下:
//sum[i]为位置i的逆序对数量
for(int i=n;i>=1;i--){
sum[i]=query(a[i]-1);
//查询该数字后面是否存在比它小的数
add(a[i],1)
//从a[i]到N的个数加1
}
这样就可以求出来每个数字后面的逆序对。要求每个数字前面的逆序对,则反着来即可。
下面以一道题目为例子
通过观察发现:首先每个小朋友交换的次数是固定的,所以先交换哪个小朋友都是可以的。其次,每个小朋友交换的次数等于每个小朋友前面比该小朋友大的个数和每个小朋友后面比该小朋友小的个数,即该小朋友前的逆序对数量和该小朋友后的逆序对数量。所以我们可以用树状数组来维护每个小朋友之前的逆序对数量和每个小朋友之后的逆序对数量,最后统计答案即可。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <stack>
#include <iomanip>
#include <unordered_map>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e6+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
constexpr lll one=1;
int a[N],c[N],sum[N];
struct BIT{
void init(){
rep(i,0,N+1) c[i]=0;
}
int lowbit(int x){
return x&-x;
}
void add(int i,int v){
while(i<=N){
c[i]+=v;
i+=lowbit(i);
}
}
ll query(int i){
ll res=0;
while(i>0){
res+=c[i];
i-=lowbit(i);
}
return res;
}
};
void solve(){
int n;
scanf("%d",&n);
BIT bit;
bit.init();
rep(i,1,n+1) scanf("%d",&a[i]);
rep(i,1,n+1){
sum[i] = bit.query(N) - bit.query(a[i]);
bit.add(a[i], 1);
}
bit.init();
rrep(i,n,1){
sum[i] += bit.query(a[i] - 1);
bit.add(a[i], 1);
}
ll res=0;
rep(i,1,n+1) res += sum[i]*(sum[i] + 1ll) / 2;
printf("%lld\n", res);
}
signed main(){
//IOS;
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。