专栏首页奇妙的算法世界树状数组求逆序对以及相关例题

树状数组求逆序对以及相关例题

求逆序对有两种方法:归并排序和树状数组,但是归并排序求得的逆序对是总共的逆序对数量,有些时候我们需要求得某个数后面的逆序对数量或者某个数前面的逆序对数量。

这种时候,则需要对归并排序进行扩展,非常的麻烦。这个时候我们就需要使用树状数组来求逆序对,使用树状数组的优势在于码量少,容易调试。但是如果值域大的话,需要进行离散化。

树状数组求逆序对的核心代码如下:

//sum[i]为位置i的逆序对数量
for(int i=n;i>=1;i--){
	sum[i]=query(a[i]-1);
	//获取[1,a[i]-1]区间内比a[i]大的个数
	add(a[i],1)
	//从a[i]到N的个数加1
}

这样就可以求出来每个数字后面的逆序对数量。要求每个数字前面的逆序对数量,则反着来即可。

下面以一道题目为例子

题意描述

题目链接

思路

通过观察发现:首先每个小朋友交换的次数是固定的,所以先交换哪个小朋友都是可以的。其次,每个小朋友交换的次数等于每个小朋友前面比该小朋友大的个数和每个小朋友后面比该小朋友小的个数,即该小朋友前的逆序对数量和该小朋友后的逆序对数量。所以我们可以用树状数组来维护每个小朋友之前的逆序对数量和每个小朋友之后的逆序对数量,最后统计答案即可。

AC代码

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树状数组求逆序对以及相关例题

    求逆序对有两种方法:归并排序和树状数组,但是归并排序求得的逆序对是总共的逆序对数量,有些时候我们需要求得某个数后面的逆序对数量或者某个数前面的逆序对数量。

    dejavu1zz
  • AcWing1081 度的数量(数位dp)

    题目链接 关于数位dp有两个技巧:第一是可以使用前缀和的思想,对于求区间 [ ...

    dejavu1zz
  • POJ 2493 (map)

    给定有n个词的字典和m个句子,每个词语除首位和末位的字母可以任意移动,求能够构成m个句子的总共不同情况有多少

    dejavu1zz
  • 树状数组求逆序对以及相关例题

    求逆序对有两种方法:归并排序和树状数组,但是归并排序求得的逆序对是总共的逆序对数量,有些时候我们需要求得某个数后面的逆序对数量或者某个数前面的逆序对数量。

    dejavu1zz
  • cf550D. Regular Bridge(构造)

    一篇写的非常好的博客:http://www.cnblogs.com/mangoyang/p/9302269.html

    attack
  • POJ - 2387 Til the Cows Come Home (最短路入门)

    Bessie is out in the field and wants to get back to the barn to get as much slee...

    风骨散人Chiam
  • cf550C. Divisibility by Eight(结论)

    设$x = 10000 * a_i + 1000 * a_{i - 1} + \dots$

    attack
  • CCF-最小差值

    种花家的奋斗兔
  • 1006 等差数列

    1006 等差数列 题目描述 Description 给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长...

    attack
  • 1006 等差数列

    1006 等差数列 题目描述 Description 给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长...

    attack

扫码关注云+社区

领取腾讯云代金券