题解：P17190 [ICPC 2017 Hong Kong R] Triangle

· · 题解

题意简述

平面上各有 n 个黑点和白点。异色点之间的边由曼哈顿距离唯一确定，同色点之间的边可以独立定向。求含两种颜色的有向三元环数量的最小值与最大值。

解题思路

一个合法三角形必然由两个同色点与一个异色点组成。先固定两个白点 x,y，考虑黑点 z。

若 z 到 x,y 的距离同时不超过 D，两条异色边都从黑点指出；若两者都超过 D，两条边都指向黑点。这两种情况都不能形成三元环。

只有恰好一个距离不超过 D 时，两条异色边方向相反。此时，x,y 之间恰有一个定向能补成有向环。

记 S_x 为与 x 距离不超过 D 的黑点集合，并定义：

c_x=|S_x|

设 k=|S_x\cap S_y|。若把白色边朝一个方向定向，产生的环数是 c_x-k；反向定向则产生 c_y-k。每条同色边可以独立选择，所以这一点对的最小、最大贡献分别为：

\begin{aligned} \min(c_x,c_y)-k \\ \max(c_x,c_y)-k \end{aligned}

对所有白点对求和时，前半部分只依赖每个白点的近邻数。交集部分可以交换枚举顺序。若黑点 z 附近有 r_z 个白点，它会同时属于这些白点集合中的任意两个，因此：

\sum_{x<y}|S_x\cap S_y|=\sum_z\binom{r_z}{2}

两黑一白的三角形完全对称。于是，求出每个点的异色近邻数后，答案就只剩一维计数。

近邻数属于 [0,n]，无需排序。设值 v 出现 m_v 次。计算所有点对的较小值之和时：

维护此前更小值的数量 pre，便能在线性时间同时计算所有点对的最小值和最大值。最后减去白点与黑点两侧的交集总和即可。

下面求异色近邻数。对每个点作坐标变换：

\begin{aligned} u & =x+y \\ v & =x-y \end{aligned}

两点的曼哈顿距离满足：

|x_1-x_2|+|y_1-y_2|=\max(|u_1-u_2|,|v_1-v_2|)

所以距离不超过 D 等价于同时满足：

\begin{aligned} |u_1-u_2| & \le D \\ |v_1-v_2| & \le D \end{aligned}

菱形查询由此变成轴平行矩形查询。

把作为数据点的一种颜色按 u 排序，并离散化它们的 v。建立可持久化线段树，第 i 个根保存前 i 个点的所有 v。对于查询点，先二分找到 u\in[u_0-D,u_0+D] 对应的两个前缀，再在两个根上查询 v\in[v_0-D,v_0+D] 的计数之差。

分别让白点查询黑点、黑点查询白点，就得到两侧全部近邻数。每次建树和查询都是 O(\log n)，总时间复杂度为 O(n\log n)，空间复杂度为 O(n\log n)。

正确性证明

固定一对同色点时，异色点只有在与二者的距离判定不同时，才产生方向相反的两条异色边。两种同色边定向分别对应集合差 S_x\setminus S_y 与 S_y\setminus S_x，所以点对的最小、最大贡献公式正确。

每条同色边只影响包含它的三角形，与其他同色边的选择无关。因此，可以对每个同色点对独立选择较小或较大贡献并求和。一个异色点被交集项计算的次数，正是从它的同色近邻中任选两个的方案数，所以交换求和后的组合数公式正确。

频率统计完整枚举了三类点对：两个值相同、前者较小、前者较大。故 calc 分别得到所有近邻数点对的最小值之和与最大值之和。

坐标变换把曼哈顿球准确变成 u,v 两维的闭区间。第 R 个持久化根包含所有 u 不超过右边界的点，第 L-1 个根包含所有 u 小于左边界的点；两次区间计数之差恰好是矩形内点数。因此，每个近邻数都被准确计算。

程序把白点对和黑点对的贡献相加，并减去各自的交集总和，所以最终最小值与最大值正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
const int M=2000005;
struct point
{
    ll x,y;
};
int n,tot;
ll d;
point a[N],b[N];
ll vx[N],vy[N];
int o[N],rt[N],ls[M],rs[M],sum[M];
int f[N],g[N],cnt[N];
int add(int p,int l,int r,int x)
{
    int u=++tot;
    ls[u]=ls[p];
    rs[u]=rs[p];
    sum[u]=sum[p]+1;
    if(l<r)
    {
        int mid=(l+r)>>1;
        if(x<=mid)ls[u]=add(ls[p],l,mid,x);
        else rs[u]=add(rs[p],mid+1,r,x);
    }
    return u;
}
int ask(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return sum[p];
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res+=ask(ls[p],l,mid,x,y);
    if(y>mid)res+=ask(rs[p],mid+1,r,x,y);
    return res;
}
void work(point q[],point p[],int c[])
{
    for(int i=1;i<=n;i++)
    {
        o[i]=i;
        vy[i]=p[i].y;
        c[i]=0;
    }
    sort(o+1,o+n+1,[&](int x,int y){return p[x].x<p[y].x;});
    for(int i=1;i<=n;i++)vx[i]=p[o[i]].x;
    sort(vy+1,vy+n+1);
    int m=unique(vy+1,vy+n+1)-vy-1;
    tot=0;
    rt[0]=0;
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(vy+1,vy+m+1,p[o[i]].y)-vy;
        rt[i]=add(rt[i-1],1,m,x);
    }
    for(int i=1;i<=n;i++)
    {
        int l=lower_bound(vx+1,vx+n+1,q[i].x-d)-vx;
        int r=upper_bound(vx+1,vx+n+1,q[i].x+d)-vx-1;
        int x=lower_bound(vy+1,vy+m+1,q[i].y-d)-vy;
        int y=upper_bound(vy+1,vy+m+1,q[i].y+d)-vy-1;
        if(l<=r&&x<=y)c[i]=ask(rt[r],1,m,x,y)-ask(rt[l-1],1,m,x,y);
    }
}
pair<ll,ll> calc(int a[])
{
    fill(cnt,cnt+n+1,0);
    for(int i=1;i<=n;i++)cnt[a[i]]++;
    ll mn=0,mx=0,pre=0;
    for(int i=0;i<=n;i++)
    {
        ll c=cnt[i];
        ll eq=c*(c-1)/2*i;
        mn+=1LL*i*c*(n-pre-c)+eq;
        mx+=1LL*i*c*pre+eq;
        pre+=c;
    }
    return {mn,mx};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin>>n>>d)
    {
        for(int i=1;i<=n;i++)
        {
            ll x,y;
            cin>>x>>y;
            a[i]={x+y,x-y};
        }
        for(int i=1;i<=n;i++)
        {
            ll x,y;
            cin>>x>>y;
            b[i]={x+y,x-y};
        }
        work(a,b,f);
        work(b,a,g);
        auto x=calc(f),y=calc(g);
        ll s=0;
        for(int i=1;i<=n;i++)
        {
            s+=1LL*f[i]*(f[i]-1)/2;
            s+=1LL*g[i]*(g[i]-1)/2;
        }
        cout<<x.first+y.first-s<<' '<<x.second+y.second-s<<'\n';
    }
    return 0;
}