洛谷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;
}