自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 22:35:44，当前版本为作者最后更新于2024-05-24 15:40:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

双倍经验（更简单）

思路

首先容易发现，两个王之间的距离为 $\max \left \{ \left |X_1-X_2 \right |,\left | Y_1 - Y_2 \right | \right \} $，直接求是 $c^2$ 的， $c$ 是点的个数，时间难以接受。

考虑进行改进，我们肯定希望能将 $\max$ 操作优化掉，联想到曼哈顿距离是 $\left | x_1 - x_2\right | +\left | y_1 - y_2\right | $，求这东西是很快的，考虑是否能将两个东西进行转化，可以将曼哈顿距离绝对值拆开，这样就存在了 $\max$，原式子就转化为 $\max\left\{x_1-x_2+y_1-y_2,x_1-x_2+y_2-y_1,x_2-x_1+y_1-y_2,x_2-x_1+y_2-y_1\right\}$

整理一下变为 $\max\left\{\left(x_1+y_1\right)-\left(x_2+y_2\right),-\left(x_1+y_1\right)+\left(x_2+y_2\right),\left(x_2+y_1\right)-\left(x_1+y_2\right),-\left(x_2+y_1\right)+\left(x_1+y_2\right)\right\}$

$\max\left\{\left|\left(x_1+y_1\right)-\left(x_2+y_2\right)\right|,\left|\left(x_2+y_1\right)-\left(x_1+y_2\right)\right|\right\}$

$\max\left\{\left|\left(x_1+y_1\right)-\left(x_2+y_2\right)\right|,\left|\left(-x_1+y_1\right)-\left(x_2-y_2\right)\right|\right\}$

$\max\left\{\left|\left(x_1+y_1\right)-\left(x_2+y_2\right)\right|,\left|\left(-x_1+y_1\right)+\left(-x_2+y_2\right)\right|\right\}$

这玩意就和之前那个 $\max \left \{ \left |X_1-X_2 \right |,\left | Y_1 - Y_2 \right | \right \} $ 很像了,$x_1+y_1=X_1,x_2+y_2=X_2,-x_1+y_1=Y_1,-x_2+y_2=Y_2$。

就可以解出 $x_1 = \frac{X_1+Y_1}{2},y_1 = \frac{X_1-Y_1}{2},x_2 = \frac{X_2+Y_2}{2},y_2 = \frac{X_2-Y_2}{2} $。

然后就转换成曼哈顿距离了。

曼哈顿距离就很好求了，将两个人分开算，直接树状数组维护比 $x$ 小的数和比 $x$ 大的数的和和个数就行了。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace IO
{
	template<typename T>
	void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
	template<typename T,typename... Args>
	void read(T &_x,Args&...others){Read(_x);Read(others...);}
	const int BUF=20000000;char buf[BUF],top,stk[32];int plen;
	#define pc(x) buf[plen++]=x
	#define flush(); fwrite(buf,1,plen,stdout),plen=0;
	template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++top]=48+x%10;while(top) pc(stk[top--]);}
}
using namespace IO;
int n,m,tot,tot1,ans,b[1000010],cnt1,c[1000010][2],c1[1000010][2],cnt,sum,sum1;
char cs;
struct w
{
	int x,y;
}a[1000010],d[1000010];
map<int,int>mp,mp1; 
inline void add(int x,int y,int y1,int id){while(x <= n*m) c[x][id]+=y,c1[x][id]+=y1,x+=x&-x;}
inline int query(int x,int id){int ans = 0; while(x) ans+=c[x][id],x-=x&-x; return ans;}
inline int query1(int x,int id){int ans = 0; while(x) ans+=c1[x][id],x-=x&-x; return ans;}
signed main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) 
		for(int j = 1;j <= m;j++)
		{
			cin >> cs;
			if(cs == 'M') a[++tot].x = i+j,a[tot].y = j-i,b[++cnt1] = a[tot].y;
			else if(cs == 'S') d[++tot1].x = i+j,d[tot1].y = j-i,b[++cnt1] = d[tot1].y;
		}
	sort(b + 1,b + 1 + cnt1);
	for(int i = 1;i <= cnt1;i++) if(!mp[b[i]]) mp[b[i]] = ++cnt;
	cnt = cnt1 = 0;
	for(int i = 1;i <= tot;i++) b[++cnt1] = a[i].x;
	for(int i = 1;i <= tot1;i++) b[++cnt1] = d[i].x;
	sort(b + 1,b + 1 + cnt1);
	for(int i = 1;i <= cnt1;i++) if(!mp1[b[i]]) mp1[b[i]] = ++cnt;
	for(int i = 1;i <= tot;i++) 
	{
		add(mp[a[i].y],a[i].y,1,0),add(mp1[a[i].x],a[i].x,1,1);
		sum+=a[i].x,sum+=a[i].y;
		ans += (2*query1(mp1[a[i].x],1)-i)*a[i].x + sum - 2*query(mp1[a[i].x],1);
		ans += (2*query1(mp[a[i].y],0)-i)*a[i].y + sum1 - 2*query(mp[a[i].y],0);
	}
	for(int i = 1;i <= tot;i++) sum-=a[i].x,sum1-=a[i].y,add(mp[a[i].y],-a[i].y,-1,0),add(mp1[a[i].x],-a[i].x,-1,1); 
	print(ans>>1); pc(' ');
	ans = 0;
	for(int i = 1;i <= tot1;i++) 
	{
		add(mp[d[i].y],d[i].y,1,0),add(mp1[d[i].x],d[i].x,1,1);
		sum+=d[i].x,sum1+=d[i].y;
		ans += (2*query1(mp1[d[i].x],1)-i)*d[i].x + sum - 2*query(mp1[d[i].x],1);
		ans += (2*query1(mp[d[i].y],0)-i)*d[i].y + sum1 - 2*query(mp[d[i].y],0);
	}
	print(ans>>1);
	flush();
	return 0;
}