洛谷P6137 [IOI2012] 理想城题解

题目链接：P6137 [IOI2012] 理想城

题意：

像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 $N$ 个区块组成，而这些区块放在一个无限大的正方形网格上。第 $x$ 行第 $y$ 列的单元格由有序数对 $(x,y)$来标识。单元格 $(0,0)$ 位于网格的左上角。给定一个单元格 $(x,y)$，与之相邻的单元格（如果存在的话）分别为：$(x-1,y)$，$(x+1,y)$，$(x,y-1)$，$(x,y+1)$。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 $(x,y)$ 上，当且仅当 $1 \le x,y \le 2^{31}-2$ 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件：

对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。

对于任意两个非空的单元格，至少存在一连串相邻的非空单元格连接它们。

以下 $4$ 个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 $3$ 个图不满足第二个条件，第 $4$ 个图两个条件均不满足。

当遍历理想城时，一个跳步代表从一个区块走到一个相邻的区块。跳步时不能移进空白单元格。假设 $v_0,v_1,\cdots,v_{N-1}$ 是 $N$ 个区块的坐标。对于任意两个不同的区块 $v_i$ 和 $v_j$，它们的距离 $d(v_i,v_j)$ 是从 $v_i$ 移动到 $v_j$ 所需的最小跳步数目。

下图是一个由 $11$ 个区块组成的理想城。区块坐标分别为

$\begin{gathered} v_0=(2,5) \quad v_1=(2,6) \quad v_2=(3,3) \\ v_3=(3,6) \quad v_4=(4,3) \quad v_5=(4,4) \\ v_6=(4,5) \quad v_7=(4,6) \quad v_8=(5,3) \\ v_9=(5,4) \quad v_{10}=(5,6) \end{gathered}$
其中，$d(v_1,v_3)=1$，$d(v_1,v_8)=6$，$d(v_6,v_{10})=2$，$d(v_9,v_{10})=4$。

给定一个理想域，试求
$S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1}d(v_i,v_j)$
输入格式：

第 $1$ 行为一个正整数 $N$，为理想城区块的数目。

第 $2$ 行到第 $N+1$ 行，每行有两个非负整数。第 $i+2$ 行为第 $i$ 个区块的坐标 $v_i = (x_i， y_i)$。

输出格式：

输出仅一行一个正整数，为 $S$ 的值。由于 $S$ 的值可能较大，你只需输出 $S$ 对 $10^9$ 取模的值。

数据范围：

$1 \le N \le 10^5$，$1 \le x_i,y_i \le 2^{31}-2$ 。

讲一个非常简单的做法。考虑将横向和纵向的贡献分开计算。

这样对于四格方格的情况，即 $(i, j),(i+1, j),(i, j+1),(i+1, j+1)$ 均为理想城区划时

我们可以把 $(i,j)$ 和 $(i,j+1)$ 之间的边切掉，这样只考虑横向/纵向时这些区划就构成一棵树。

那么只需要暴力建树然后跑一遍 dfs 就能算出来了，一条边的贡献就是左右子树的大小之积。

时间复杂度 $\mathcal{O}(n \log n)$ ，因为连边需要用一下 map 。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 1e9; // wow!
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(ll &x, ll y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define Fi first
#define Se second
#define N ((int)(1e5 + 15))

int n, x[N], y[N], sz[N]; ll res;
map< int, map<int, int> >mp; vector<pii> vec[N];
void dfs(int u, int fa)
{
    sz[u] = 1;
    for(auto i : vec[u]) if(i.Fi != fa)
    {
        const int v = i.Fi, w = i.Se;
        dfs(v, u); sz[u] += sz[v];
        add(res, 1ll * sz[v] * (n - sz[v]) * w % mod);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n) cin >> x[i] >> y[i];
    for(int j = 0; j <= 1; dfs(1, 0), j++)
    {
        mp.clear(); rep(i, 1, n) vec[i].clear();
        rep(i, 1, n) { swap(x[i], y[i]); mp[x[i]][y[i]] = i; }
        rep(i, 1, n)
        {
            int t = mp[x[i] + 1][y[i]];
            if(t) { vec[t].pb({i, 0}); vec[i].pb({t, 0}); }
            t = mp[x[i]][y[i] + 1];
            if(t && !(mp[x[i] - 1][y[i]] && mp[x[i] - 1][y[i] + 1]))
                { vec[t].pb({i, 1}), vec[i].pb({t, 1}); }
        }
    }
    cout << res << '\n';
    return 0;
}