自动搬运

查看原文

来自洛谷，原作者为

	SDSXC 打表代替思考，观察代替推导，等等，计数是什么？

搬运于2025-08-24 23:16:05，当前版本为作者最后更新于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;
}