一种基于容斥原理的n^2logn后优化求全子区间逆序对

RimingMist · 2026-01-05 16:03:00 · 算法·理论

零、题外话

考场上自己乱想的，甚至其中的一个步骤我都不能解释清楚为什么这么做 （因为是我自己手模出来的）。

好，回归正题。

我这里的“区间逆序对”其实不是标准的。当我们需要 每一个区间 的逆序对的时候，我这种神秘的 O(n^2 \log n) 预处理，O(1) 查询做法应该是比较优秀的（其实时间复杂度没有那么多，少得多）。但是，空间并不优秀，是 O(n^2) 的。这就导致了我考场上 MLE 了两个点，并且是捆绑测试…

这里由于时间复杂度和空间复杂度不够优秀，于是我进行了更新，优化掉了一个 log，不过在阅读一种基于容斥原理求全子区间逆序对的优化之前，请先阅读本文章以进行了解（本来想单独出文章的，但是有点短，不够优质，没过审...）。

一、求逆序对的公式

这个算法基于一个公式，接下来，我们定义：

• 为了过审，我们定义 \text{inv}(C) 表示序列 C 的逆序对个数。

假设我们求 A 数组，数组起点为 1，最后一个为 n，那么我们有区间 i \sim j 的逆序对个数：

怎么感觉这个 markdown 怪怪的

其实核心部分我已经讲完了…

给大家讲讲原理：

基于容斥原理。

众所周知，如果要求 i 到 j 的和，就是：（1 到 j 的和）+（i 到 n 的和）-（1 到 n 的和）。其中 n 是最后一个。

这个也差不多，前面的 \text{inv}(A[1 \sim j]) + \text{inv}(A[i \sim n]) 和上文一样，但是为什么还要 \sum_{k=1}^{i-1} \text{inv}(\{A[k], A[(j+1) \sim n]\}) 呢？

这里是我最疑惑的。我们想要从多余中找到区间逆序对，不能直接用容斥原理，因为 A[1] 至 A[i-1] 的每一个数都会和 A[j+1] 至 A[n] 产生逆序对。这些多的没有算上，需要加上。

其实就是一个简单（kun nan）容斥原理。

接下来我们试试怎么编码。

二、代码实现

为了求逆序对，我使用了树状数组：

int mp[5002];
inline void update(int x,int v){
    while(x<=10002)mp[x]+=v,x+=lowbit(x);
}
inline ll query(int x){
    ll res=0;
    while(x)res+=mp[x],x-=lowbit(x);
    return res;
}

以及一些数组：

ll fan[5002];//fan[i]代表数组a[i]~a[n]的逆序对个数
ll zheng[5002];//zheng[i]代表数组a[1]~a[i]的逆序对个数
ll node[5002][5003];//node[i][j]代表a[j]~a[n]中比i小的。注意，这里是i，不是a[i]
ll all[5002][5002];//all[i][j]代表{a[1],a[r]~a[n]}的逆序对个数+...+{a[l],a[r]~a[n]}的逆序对个数
ll nx[5002][5003];//nx[i][j]代表a[i]~a[j]的逆序对个数

这里我不得不讲一讲 all。当我们算 \sum_{k=1}^{i-1} \text{inv}(\{A[k], A[(j+1) \sim n]\}) 时，我们只需要提前预处理记录 1 \sim i 和 (j+1) \sim n 产生的没算完的个数，也就是那一大堆的结果。那么我们只需要记录一个二维数组 [i][j] 即可。

第一部分：求 \text{inv}(A[1 \sim n])， 顺便把 \text{inv}(A[i \sim n]) 的逆序对个数求了。

    int n;cin>>n;
    pair<int,int> in[n+1];int a[n+1];
    for(int i=1;i<=n;i++) cin>>in[i].first,in[i].second=i;
    sort(in+1,in+1+n);
    int tmp=0;
    for(int i=1;i<=n;i++){
        if(i==1||in[i].first!=in[i-1].first){
            tmp++;
        }a[in[i].second]=tmp;
    }//离散化
    //求整体和fan逆序对
    ll num=0;//num存整体
    for(int i=n;i>=1;i--){
        ll tmp=query(a[i]-1);
        fan[i]+=tmp+fan[i+1];//这个很好理解吧...后面一个加上当前点产生的逆序对个数
        num+=tmp;
        update(a[i],1);
    }

第二部分：求 \text{inv}(A[1 \sim j])。

    memset(mp,0,sizeof mp);//清空树状数组
    for(int i=1;i<=n;i++){
        update(a[i],1);//再来一次
        zheng[i]=zheng[i-1]+query(10005)-query(a[i]);//其实就是正着算逆序对的方法。时间复杂度比反着算差一点。
    }

最难算的就是 \sum_{k=1}^{i-1} \text{inv}(\{A[k], A[j+1 \sim n]\}) 这一大堆了。它难算在于又要求一次区间。又成了区间问题。所以接下来两个部分都在求这个。

第三部分：求 node。这里就是时间复杂度的瓶颈了，是 n^2 \log _n 的。

    memset(mp,0,sizeof mp);//清空树状数组
    for(int i=n;i>=1;i--){
        update(a[i],1);//倒着求，一样的
        for(int j=1;j<=i-1;j++){//node是为了求all的，不需要每一个数字，所以优化了这里。不然每一次都要跑n次。
            node[a[j]][i]=query(a[j]-1);//看目前在i之后比a[j]小的。（因为求到了i这个位置）
        }
    }

第四部分：求 all。

    for(int i=n;i>=1;i--){
        ll tmp=0;//记录目前算下来有几个符合的
        for(int j=1;j<i;j++){
            tmp+=node[a[j]][i];//加上第i位之后比a[j]小的
            all[j][i]=tmp;//因为是累加，所以可以直接得到
        }
    }

第五部分：求 nx。直接套用公式就可以了。

    for(int l=1;l<=n;l++){
        for(int r=l+1;r<=n;r++){
            nx[l][r]=(zheng[r]+fan[l]+all[l-1][r+1]-num);//就是那个公式
        }
    }

nx 中就存储了每一段区间的值啦！

这个算法可能并非时间复杂度是最优秀的，但是这是一种思维方式，即区间计数问题可以考虑使用容斥原理。这份代码或许有优化的地方，Gemini 说可以区间 DP 是 O(n^2) 的，敬请指出！

这是我的废稿（格式不对）：一种神秘的 n^2 求每一个区间的逆序对（稿子）