P6137 [IOI2012]理想城 题解

· · 题解

题目大意：无限大的网格上有两种格子，满足所有黄格子四联通，所有白格子四联通，两个黄格子 x 和 y 的距离 d(x,y) 指只走黄格子从 x 到达 y 的最短路径长度，总共 N 个黄格子，求 \sum_{1≤i<j≤N}d(i,j)。

分析：首先把图按行剖分，连在一起的格子缩成一个点，上下相邻的点连边，由于本题中图的特殊性质，连边后不会有环，而且是一棵树。在这棵树上 DP，设节点 i 子树大小为 S_i，则答案为 \sum_{i=1}^N S_i(N-S_i)，因为子树内的所有点与子树外的所有点两两都要走一遍这条边。这样就可以统计出纵向边的贡献。将图翻转 90^{\circ}，再做一遍统计横向边贡献。

实现：将 N 个格子以 x 坐标为第一关键字、以 y 坐标为第二关键字排序，合并成块，要记录格子所属块的编号，建树后 DP 即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
#define t(x,y) (x)*n+y
#define min(a,b) a<b?a:b
#define mod 1000000000
#define M 3200000
using namespace std;
struct node1{int x,y;}v[100005];
struct node2{int x,l,r;}s[M];
bool cmp(node1 a,node1 b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
int mx=1e9,my=1e9;
int n,h[M],ne[M*2],to[M*2],tot=0,cnt=0;
map<int,int>bz;
ll ans=0,size[M];
void add(int a,int b)
{
    to[++tot]=b,ne[tot]=h[a],h[a]=tot;
    to[++tot]=a,ne[tot]=h[b],h[b]=tot;
}
void dfs(int u,int fa)
{
    size[u]=s[u].r-s[u].l+1;
    for(int i=h[u];i;i=ne[i])
    {
        if(to[i]==fa)continue;
        dfs(to[i],u),size[u]+=size[to[i]];//统计子树大小
    }
    for(int i=h[u];i;i=ne[i])
    {
        if(to[i]==fa)continue;
        ans=(ans+(n-size[to[i]])*size[to[i]]%mod)%mod;//统计贡献
    }
}
void init()
{
    for(int i=1;i<=n;i++)v[i].x-=mx-1,v[i].y-=my-1;//将整个图平移
    sort(v+1,v+1+n,cmp),cnt=1,s[1].x=v[1].x,s[1].l=s[1].r=v[1].y,bz[t(v[1].x,v[1].y)]=1;
    for(int i=2;i<=n;i++)//分块
    {
        if(v[i-1].x==v[i].x&&v[i-1].y+1==v[i].y)
        {
            bz[t(v[i].x,v[i].y)]=cnt,s[cnt].r=v[i].y;
        }
        else s[++cnt].x=v[i].x,s[cnt].l=s[cnt].r=v[i].y,bz[t(v[i].x,v[i].y)]=cnt;
    }
    for(int i=1;i<=cnt;i++)//建树
    {
        for(int j=s[i].l;j<=s[i].r;j++)
        {
            if(bz[t(s[i].x+1,j)])add(i,bz[t(s[i].x+1,j)]),j=s[bz[t(s[i].x+1,j)]].r;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&v[i].x,&v[i].y),mx=min(mx,v[i].x),my=min(my,v[i].y);
    init();
    dfs(1,0);
    bz.clear(),tot=0,cnt=0,memset(h,0,sizeof(h)),memset(size,0,sizeof(size));
    for(int i=1;i<=n;i++)v[i].x+=mx-1,v[i].y+=my-1,swap(v[i].x,v[i].y);
    swap(mx,my);
    init();
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}