题解：P8075 [COCI2009-2010#7] KRALJEVI

kkxacj · 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-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;
}