自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:37:20，当前版本为作者最后更新于2022-04-02 18:33:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Preface

二维偏序解法。来一篇代码简单一点的题解，代码长度 $1.12$ KB。

Analysis

正难则反。我们很难正向计算每个数的贡献（三维偏序），那么我们假设所有数对 $\max$ 和 $\min$ 都有贡献，则答案为 $2n\times sum$，这个很容易计算。

接下来我们要减去没有对 $\max$ 产生贡献的与没有对 $\min$ 产生贡献的数。假设现在有三个数组 $A,B,C$。我们要算对于 $B$ 中的每一个数 $B_i$，有多少个 $j$ 满足一下条件：

$$\begin{cases} A_i+A_j\le B_i+B_j\\ B_i+B_j\le C_i+C_j \end{cases} $$

移项一下，得：

$$\begin{cases} A_i-B_i\le B_j-A_j\\ B_i-C_i\le C_j-B_j \end{cases} $$

这是一个二维偏序问题，可以 $O(n\log n)$ 解决。

所以我们只要枚举任意有序的三个数组，进行上述算法即可算出所有不合法的数的总和，减去即可。时间复杂度 $O(n\log n)$，带一个 $24$ 的常数。

需要注意的是，可能有相等的数，执行上述算法两者都会被减去，因此强制规定：若两个数相同，编号小的数组中的元素 $<$ 编号大的数组中的元素。

Code

Talk is cheap, show me the code.

奉上极简代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define N 200010
#define base 200001
int n,m,a[4][N],ans=0,c[2*N],tot;
struct que{
	int op,x,y,val;
	bool operator<(const que &p)const{
		if(x!=p.x) return x<p.x;
		return op<p.op;
	}
}q[400010];
void upd(int x){
	while(x<2*base) c[x]++,x+=x&(-x);
}
int qry(int x){
	int res=0;
	while(x) res+=c[x],x-=x&(-x);
	return res;
}
int calc(int x,int y,int z){
	int res=0;
	memset(c,0,sizeof(c)),tot=0;
	For(i,1,n){
		q[++tot]=(que){0ll,a[x][i]-a[y][i]+(x>y),a[y][i]-a[z][i]+(y>z),0ll};
		q[++tot]=(que){1ll,a[y][i]-a[x][i],a[z][i]-a[y][i],a[y][i]};
	}
	sort(q+1,q+tot+1);
	For(i,1,tot){
		if(q[i].op==0) upd(q[i].y+base);
		else res+=q[i].val*qry(q[i].y+base);
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>m>>n;
	For(i,0,m-1) For(j,1,n) cin>>a[i][j];
	For(i,m,3) For(j,1,n) a[i][j]=a[i-m][j];
	For(i,0,3) For(j,1,n) ans+=2*n*a[i][j];
	For(i,0,3) For(j,0,3) For(k,0,3) if(i!=j&&j!=k&&k!=i) ans-=calc(i,j,k);
	cout<<ans;
}