树状数组和逆序对

逆序对的概念

  在一个有 (n) 个元素的数组 (A) 中,如果存在 (1 leqslant i <j leqslant n) ,使得 (A_i > A_j) ,则称 (<A_i,A_j>)(A) 的一个逆序对。我们熟知的排序其实就是一个消灭逆序对的过程。求一个数组的逆序对数目,我们可以用归并排序,或者用我们今天的主角树状数组,还不会树状数组的同学可以看我之前的一篇学习笔记的博客(戳这里),很快就可以理解了。

树状数组打逆序对

  • 洛谷 P1908 逆序对
  • 牛客 NC15163 逆序数

  两题都是求逆序对的模板题,洛谷数据被加强过,而且数字范围更大,如果用树状数组做需要进行离散化操作,而归并排序不用,这也是归并排序更快的原因。但是有的时候归并排序不能维护一些区间信息(见下一题)。
  先来分析一下逆序对应该怎么数。把逆序对的概念换一种更通俗的说法,逆序对其实就是由一个数和之前比它大的数组成。朴素的做法就是在每一个数插入的时候,遍历它前面的每一个数,如果比它大答案就加一。这种做法显然是 (O(n^2)) 的,而 (n) 的范围是 (10^5) 级别的,肯定冲不过去。为了把时间复杂度降到 (O(nlogn)) 级别,我们需要使用线段树和树状数组来维护。线段树在这里就有点麻烦了,我们用更简洁的树状数组就可以了。每插入一个数,是单点修改;每查询一个数之前比它大的数目,是区间查询,可行!
  树状数组传统代码,修改和查询完全不变:

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 5e6+9;
ll  t[maxn],ans;
int n,m,num[maxn];

void update(int now){
    while(now<=m){
        t[now] ++;
        now += lowbit(now);
    }
}

ll query(int now){
    ll an = 0;
    while(now){
        an += t[now];
        now -= lowbit(now);
    }
    return an;
}

int main(){
    speedUp_cin_cout//加速读写
    cin>>n;
    For(i,1,n) cin>>num[i],m = max(m,num[i]);
    For(i,1,n) {
        //先查询比它大的数的数目,query(m)是总数,query(num[i])是小于等于num[i]的数的数目,相减可得
        ans += query(m)-query(num[i]);
        //再加入树状数组
        update(num[i]);
    }
    cout<<ans;
    return 0;
}

  然而这个代码只能过牛客那题,交到洛谷是全紫 (RE) 的 (ノへ ̄、) 。原因其实就是 (num[i]) 的上限是 (10^9) ,导致树状数组越界了。解决方法很简单,因为我们只关心数字之间的关系,并不关心他们的实际大小,所以我们对输入数据进行一下离散化,把大数映射成小数,如果你没接触过离散化也没关系,看一遍就懂了,不懂可以看一下其他博客哦。
  修改主函数代码,即可解决洛谷模板题:

//离散化数组,可以用vector
vector<int>a;
int main(){
    speedUp_cin_cout//加速读写
    cin>>n;
    For(i,1,n) cin>>num[i],a.push_back(num[i]);
    //先排序
    sort(a.begin(),a.end());
    //再去重,固定写法
    a.erase( unique( a.begin(),a.end() ) ,a.end());
    //获得去重后的数组大小,即不同的数有多少个
    m = a.size();
    For(i,1,n) {
        //确定num[i]在去重后升序排列的数组中的位置,这里注意要加1,因为树状数组从1开始存
        num[i] = lower_bound(a.begin(),a.end(), num[i] ) - a.begin()+1;
        //先查询比它大的数的数目,query(m)是总数,query(num[i])是小于等于num[i]的数的数目,相减可得
        ans += query(m)-query(num[i]);
        //再加入树状数组
        update(num[i]);
    }
    cout<<ans;
    return 0;
}

子区间逆序对

  • NC14522 珂朵莉的数列

  同样是求逆序对,这题却要求我们求所有子区间的逆序对个数,肯定是不能用刚刚的方法直接暴力 (O(n^3logn))。我们考虑一次遍历数组就可以把每个逆序对的贡献算出来,让时间复杂度还是 (O(nlogn)) 的。
  对于一个逆序对 (<A_i,A_j>) ,只有 $l in [1,i] ,r in [j,n] $ 构成的子区间 ([l,r]) 才能包含这个逆序对,也就是话说一个逆序对对总答案的贡献就是 (i * (n-j+1)),即包含它的子区间数目。由上一题我们可以知道,当我们遍历到 (A_j) 的时候,可以用树状数组查询大于 (A_j) 的数的数目。而在这里我们仅仅维护数目是不行的,因为每个数的贡献还和它的位置有关。而分析上面那个逆序对贡献的式子,只要知道 (A_i) 的下标 (i) 即可。那么我们就用树状数组来维护每个数的下标和,这样就可以一次遍历求出答案了。
  还要注意这道题爆 (long~ long) 了(最近总是遇到刚好爆 (long~ long) 的题,有心理阴影了),我又不舍得打高精度,只好用奇技淫巧 $__int128 $了,但是要注意 $__int128 $ 类型是不能用 (cin、cout、scanf、printf) 的,要自己手写输入输出,这里不用输入,我写了一个输出。

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 5e6+9;
lll  t[maxn];
int n,m,num[maxn];
vector<int>a;

void update(int now,int value){
    while(now<=m){
        t[now] += value;
        now += lowbit(now);
    }
}

ll query(int now){
    ll an = 0;
    while(now){
        an += t[now];
        now -= lowbit(now);
    }
    return an;
}

//__int128输出
void print(lll x){
    if(x == 0) return;
    print(x/10);
    int tem = x%10;
    cout<<tem;
}

int main(){
    speedUp_cin_cout
    cin>>n;
    For(i,1,n) cin>>num[i],a.push_back(num[i]);
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    m = a.size();
    lll ans = 0;
    For(i,1,n) {
        num[i] = lower_bound(a.begin(),a.end(),num[i])-a.begin()+1;
        //计算比num[i]大的数的坐标和
        lll l = (query(m)-query(num[i]));
        //右边部分的区间长度
        lll r = n-i+1;
        ans += l*r;
        //加入坐标
        update(num[i],i);  
    }
    if(ans) print(ans);
    else cout<<0;
    return 0;
}

逆序对和排序问题

  • P1966 火柴排队
  • NC16526 火柴排队

题意概括

  有两列都是 (n) 根的火柴,同一列高度互不相同,将两列火柴直接的距离定义为 (sumleft(a_{i}-b_{i}right)^{2}) 。其中 (a_i) 表示第一列火柴中第 (i) 个火柴的高度,(b_i) 表示第二列火柴中第 (i) 个火柴的高度。仅可以交换相邻两根火柴的位置,求要让两列火柴距离最小的最小交换次数,并对 (10^8-3) 取模。数据满足 (1 leq n leq 10^{5}, 0 leq) 火柴高度 (<2^{31})

分析

  这道题看起来和逆序对好像没有什么关系,需要一些分析后才可以和逆序对联系起来。
  首先我们要分析出什么时候火柴距离最小。展开火柴距离的式子:

[begin{array}{c}
sum_{i=1}^{n}left(a_{i}-b_{i}right)^{2} \
=sum_{i=1}^{n}left(a_{i}^{2}-2 a_{i} b_{i}+b_{i}^{2}right) \
=sum_{i=1}^{n}left(a_{i}^{2}+b_{i}^{2}right)-sum_{i=1}^{n}left(2 a_{i} b_{i}right)
end{array}]

  因为所有火柴高度已经定下来了,即 (sum_{i=1}^{n}left(a_{i}^{2}+b_{i}^{2}right)) 大小不会随着交换而改变。所以我们要最大化 (sum_{i=1}^{n}left(2 a_{i} b_{i}right)) 才能使这个式子最小。根据排序不等式,我们知道同序和 (geqslant) 乱序和 (geqslant) 逆序和(证明可以自行百度,会用就行了)。所以我们要让火柴排成“同序和”的顺序即可。换句话说,假如我们仅交换 (b) 列火柴(交换 (a)(b) 是等效的,我们选一列交换,让另一列不动就行)就是让 (b) 的第 (i) 小与 (a) 的第 (i) 小怼齐。
  这其实是一种排序,认识到这一点很重要。我们原来平时的排序,以升序为例,其实是把下标当做一个标准序列 (standard[~]={1,2,3,···,n}) ,然后把要排序的数组 (num) 按照 (standard) 从小到大怼齐,也就是 (num) 的第 (i) 小与 (standard) 的第 (i) 小怼齐。而在只能进行相邻交换的前提下,最小的交换次数就是 (num) 的逆序对数目(可以自己感性证明一下)。现在我们把标准序列的定义换成一个指示 (a) 的第 (i) 小的位置的数组,即 (a[~standard[i]~])(a) 的第 (i) 小,要排序的数组定义改为指示 (b) 的第 (i) 小的位置的数组 ,即 (b[~num[i]~])(b) 的第 (i) 小。然后新建一个序列 (q),让 (q[~standard[i]~] = num[i]) ,即让 (num[~]) 按照 (standard[~]) 进行“排序”,最终答案就是 (q) 的逆序对数目。
  这里是比较难理解的,需要自己列几个例子辅助思考。剩下部分其实就是求逆序对的模板。虽然数据范围很大,但是我们用了一种特殊的离散化方式,将离散化数组 (p_i) 定义为 (a)(b) 的第 (i) 小的位置(也就是上文中的 (standard)(num))。

(Code:)

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 2e5+9;
const int mod = 1e8-3;
int a[maxn],b[maxn],q[maxn],pa[maxn],pb[maxn];
ll t[maxn],n;

void update(int now){
    while(now <= n){
        t[now]++;
        now += lowbit(now);
    }
}

ll query(int now){
    ll an = 0;
    while(now){
        an =  (an + t[now])%mod;
        now -= lowbit(now);
    }return an;
}
bool cmp1(int &x,int &y){
    return a[x] < a[y];
}
bool cmp2(int &x,int &y){
    return b[x] < b[y];
}
int main(){
    speedUp_cin_cout  //读写优化
    cin>>n;
    For(i,1,n) cin>>a[i],pa[i] = i;  //pa,pb为离散化数组
    For(i,1,n) cin>>b[i],pb[i] = i;
    sort(pa+1,pa+1+n,cmp1);
    sort(pb+1,pb+1+n,cmp2);
    For(i,1,n)  q[pa[i]] = pb[i];      //新建序列
    ll ans = 0;
    //求q的逆序对
    For(i,1,n){
        ans = (((query(n) - query(q[i]))%mod + ans)%mod+mod)%mod;
        update(q[i]);
    }
    cout<<ans<<endl;
    return 0;
}

总结

  逆序对和树状数组的联系还是挺大的,很多涉及逆序对的题目都可以尝试用树状数组冲一下,当然归并排序也是一定要掌握的啦。

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 树状数组和逆序对

发表评论

免登录下载网,提供全网最优质的资源集合!