P3157 [CQOI2011] 动态逆序对 题解

· · 题解

鲜花

虽然说这道题已经有一车题解了，仔细翻了下好像还没有这种。

分析

考虑根号重构，先来一个简单版本：

在一个长度为 n 的序列中删除一个数，求逆序对。

这非常简单，对于第 i 个数 a_i，我们求出 ctb_i=\left(\sum\limits_{j=1}^{i-1} [a_j>a_i]\right)+\left(\sum\limits_{j=i+1}^{n} [a_j<a_i]\right)，即 a_i 对答案 ans 的贡献，再用答案减去 ctb_i 即可。

那如果我们删除若干个数呢？

假设依次删除了 a_{p_1},a_{p_2},\cdots,a_{p_k} 这些数，答案就是 ans- \left(\sum\limits_{i=1}^{k} ctb_{p_i}\right) +\left(\sum\limits_{i=1}^{k} [(a_{p_i}>a_{p_k}\land p_i <p_k)\lor(a_{p_i}>a_{p_k}\land p_i <p_k)]\right)。

后面一个 \sum 其实就是序列 \{a_{p_i}\}_{i=1}^{k} 的逆序对个数。

其实难维护的也是后面一个 \sum，这等价于动态二维偏序，直接把它当三维偏序就好了。如果把每 B 个修改分成一块，暴力做就可以得到 O(mB) 的复杂度。

这启发我们利用根号重构的技巧，总时间复杂度为：O\left(\dfrac{m}{B}\cdot n\log n+mB\right)，取 B=\sqrt{n\log n} 有最优复杂度 O\left(m\sqrt{n\log n}\right)。

代码

#include "cstdio"
#include "iostream"
#include "algorithm"
#include "cmath"
#include "cstring"
using namespace std;
const int maxn=1e5+5,len=2000;
int ord[maxn],a[maxn],ctb[maxn],bit[maxn],del[maxn],n,m,cnt;
bool vis[maxn];
inline void add(int i,int v) {for(;i<=n;i+=i&-i) bit[i]+=v;}
inline int ask(int i) {int r=0; for(;i;i-=i&-i)r+=bit[i]; return r;}
inline void getans(int q) {
    long long ans=0;
    memset(ctb,0,sizeof(int)*(n+5));
    memset(bit,0,sizeof(int)*(n+5)); 
    for(int i=1,cnt=0;i<=n;++i) if(!vis[i]) {
        ctb[i]+=cnt-ask(a[i]); add(a[i],1); ++cnt;
        ans+=ctb[i];
    }
    memset(bit,0,sizeof(int)*(n+5));
    for(int i=n;i;--i) if(!vis[i]) {
        ctb[i]+=ask(a[i]); add(a[i],1);
    }
    for(int i=1;i<=q;++i) {
        cout<<ans<<'\n';
        ans-=ctb[ord[del[i]]]; vis[ord[del[i]]]=1;
        for(int j=1;j<i;++j) {
            if(ord[del[j]]<ord[del[i]]&&del[j]>del[i]) ++ans;
            if(ord[del[j]]>ord[del[i]]&&del[j]<del[i]) ++ans;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i],ord[a[i]]=i;
    for(int i=1;i<=m;++i) {
        cin>>del[++cnt];
        if(cnt==len) getans(cnt),cnt=0;
    }
    if(cnt) getans(cnt);
    cerr<<1.0*clock()/CLOCKS_PER_SEC;
    return 0;
}