题解：P12507 「ROI 2025 Day2」最小化逆序对

SDSXC · 2025-07-06 01:07:23 · 题解

逆天卡常题，教我根号过 2\times 10^6。

以下不妨设 n\leq m，即 n\leq \sqrt{nm}。

首先我们容易设计 dp 状态，令 f_{i,j} 表示删了 i 行，j 列。但是这样统计贡献的时候需要处理一个 L 形的东西，非常烦人，我们考虑把整个过程倒过来，将矩阵右下和左上翻转一下，每次添加向下一行或者向左添加一列，最小化顺序对数。

添加一行(列)的时候顺序对数显然的会增加这一行(列)与原有部分之间的顺序对，以及这一行(对)内部的顺序对数。后者是好算的，随便搞个树状数组暴力统计就是 O(nm(\log nm)) 的。接下来主要考虑前者怎么算。

如图，假设红色部分是我们新添加的一列，我们把最后一行分离出来(黄线)，我们要统计的是 A,B 与 C,D 之间的贡献，显然可以拆成，A 与 C，A 与 D，B 与 C，B 与 D 四个部分的和，A 与 C 之间的前面已经算过了，直接拿来用，B 与 D 之间的之前统计行内贡献的时候也算过，直接差分一下即可。

A 与 D 之间的是一个三维偏序，可以对值域扫描线然后用二维树状数组统计，O(nm\log n \log m)。

B 与 C 之间的，我们考虑枚举每一行，然后从左至右扫描线，依次添加 B 中元素，然后暴力枚举 C 中的元素。也就是要支持 O(n^2m) 次单点加，O(nm) 次前缀和，分块可以做到 O(n^2m+(nm)^{1.5})。

这样精细实现优化一下连续性可能能过，但是有可能会被卡常，所以我们需要做一些小优化。前面的 polylog 部分不在瓶颈上，没什么卡的必要，主要考虑分块部分，注意到每个位置的值仅有 0 或 1，考虑一个类似压位树状数组的东西，将 64 位压成一位，然后前面 64 的整数倍部分正常分块，最后不满 64 位的部分利用位运算 O(1) 的查，可以优化到 O(n^2m+\frac{(nm)^{1.5}}{\sqrt{w}})。虽然没有次数上的优化，但是常数小了将近一半。

#include<bits/stdc++.h>
#define N 2000009
#define SN 1450
#define ll long long
#define vec vector
#define ull unsigned ll
#define popcnt __builtin_popcountll
using namespace std;
ull mk[70];
struct BLOCK2{
    ull b[(N>>6)+5];
    int a[(N>>6)+5],c[(SN>>3)+2],be[(N>>6)+5],L[SN],R[SN],B,C,n;
    void init(int _n){
        n=_n/64+1;B=min(n,int(sqrt(n)*1.25+1));C=(n+B-1)/B;
        for(int i=1;i<=C;i++){
            L[i]=R[i-1]+1;R[i]=min(n,R[i-1]+B);
            for(int j=L[i];j<=R[i];j++)be[j]=i;
        }
    }
    void clear(){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
    }
    void add(int x){
        int y=(x>>6)+1;
        for(int i=be[y];i<=C;i++)c[i]++;
        for(int i=y;i<=R[be[y]];i++)a[i]++;
        b[y]|=1ull<<(x&63);
    }
    inline int sum(int x){
        return c[be[(x>>6)]-1]+a[(x>>6)]+popcnt(b[(x>>6)+1]&mk[x&63]);
    }
} T3;
vec<int> a[SN],b[N],p[SN],q[SN];
int n,m,S,pos[N][2];
vec<ll> f[SN];
struct BIT2{
    vec<int> c[SN];
    void add(int x,int y){
        for(;x<=n;x+=(x&-x)){
            for(int z=y;z<=m;z+=(z&-z))c[x][z]++;
        }
    }
    int sum(int x,int y){
        int ret=0;
        for(;x;x-=(x&-x)){
            for(int z=y;z;z-=(z&-z)) ret+=c[x][z];
        }
        return ret;
    }
} T2;
struct BIT{
    int c[N];
    void add(int x,int v){
        for(;x<=S;x+=(x&-x)) c[x]+=v;
    }
    int sum(int x){
        int ret=0;for(;x;x-=(x&-x)) ret+=c[x];return ret;
    }
} T1;
vec<array<ll,2>> g[SN],w[SN];
void init(){
    for(int i=0;i<=n;i++){
        f[i].resize(m+2);
        g[i].resize(m+2);
        p[i].resize(m+2);
        q[i].resize(m+2);
        w[i].resize(m+2);
        a[i].resize(m+2);
        T2.c[i].resize(m+2);
    }
    for(int i=0;i<=m;i++){
        b[i].resize(n+2);
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    mk[0]=1;for(int i=1;i<64;i++)mk[i]=mk[i-1]|(1ull<<i);
    cin>>n>>m;S=n*m;
    if(n>m){
        swap(n,m);
        init();
        for(int j=m;j;--j){
            for(int i=n;i;--i)cin>>a[i][j];
        }
    }
    else{
        init();
        for(int i=n;i;--i){
            for(int j=m;j;--j)cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)b[j][i]=a[i][j],pos[a[i][j]][0]=i,pos[a[i][j]][1]=j;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            g[i][j][1]=g[i][j-1][1]+T1.sum(a[i][j]);
            T1.add(a[i][j],1);
        }
        for(int j=1;j<=m;j++){
            T1.add(a[i][j],-1);
        }
    }
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            g[i][j][0]=g[i-1][j][0]+T1.sum(b[j][i]);
            T1.add(b[j][i],1);
        }
        for(int i=1;i<=n;i++){
            T1.add(b[j][i],-1);
        }
    }
    for(int i=1;i<=S;i++){
        p[pos[i][0]][pos[i][1]]=T2.sum(pos[i][0]-1,pos[i][1]-1);
        T2.add(pos[i][0],pos[i][1]);
    }
    T3.init(S);
    for(int i=1;i<=n;i++){
        T3.clear();
        for(int j=1;j<=m;j++){
            ll t=0;for(int k=1;k<i;k++)t+=T3.sum(b[j][k]);
            q[i][j]=t;
            T3.add(a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            w[i][j][0]=w[i-1][j][0]+p[i][j]+q[i][j]+g[i][j][1]-g[i][j-1][1];
            w[i][j][1]=w[i][j-1][1]+p[i][j]+(i-1)*(j-1)-q[i][j]+g[i][j][0]-g[i-1][j][0];
            f[i][j]=min(f[i][j-1]+w[i][j][0]+g[i][j][0],f[i-1][j]+w[i][j][1]+g[i][j][1]);
        }
    }
    cout<<f[n][m]<<"\n";
    return 0;
}