问题

给出平面上若干个点，两点之间的距离为两点之间的曼哈顿距离，求这些点的最小生成树
例题传送门
两点的曼哈顿距离： $dis_{ij}=\left|x_i-x_j\right|+\left|y_i-y_j\right|$

定理

对于图上任意一个环，环上边权最大的边一定不在最小生成树上
证明：
- 环上至少有一条边不在最小生成树上，若环上所有边都在最小生成树上，那不满足树的性质
- 在树上任意断开一条边，最小生成树必然分成两棵子树
- 假设环上边权最大的边在最小生成树上，在最小生成树上断开这条最大的边，新产生的两棵子树显然可以通过连接原先环上的边重新形成一棵树，而这条边的权值显然小于已经断开的边，所以总权值变小了，与原先的树是最小生成树相矛盾

做法

分析

根据上述定理，显然图中的蓝色边是不需要连接的，它不可能出现在最小生成树的答案中
对于每个点，以它作为原点，以图示区域为例，因为所有边都是无向边，所以只需要连接这个区域内离它最近的点，也就是只需要连接绿色边

以图示区域为例
设原点上的点为 $i$ ,则对于其余点 $k$
显然有 $\left.\begin{cases} x_i\le x_k\\ x_k-x_i\le y_k-y_i \end{cases}\right.$
于是有 $y_i-x_i\le y_k-x_k$
显然对于满足条件的 $k$ , $dis_{ik}=x_k+y_k-(x_i+y_i)$
所以我们只需要对每个点按照 $y-x$ 离散后,对点按照 $x$ 降序排序在线段树或者树状数组上维护 $\ge x+y$ 的最小值，查询后插入当前点即可

完善

对于一个二维平面，显然可以划分为这样 $4$ 个区域
图片说明对于 $x$ 轴右侧的区域，可以通过交换点枚举顺序的方法处理

区域 $1$ 就是上述的例子
区域 $2$ 的点可以通过关于直线 $y=x$ 对称变换到区域 $1$ 中
区域 $3$ 的点可以通过在区域 $2$ 的变换的基础上关于 $x$ 轴对称得到
区域 $4$ 的点可以通过在区域 $3$ 的变换的基础上，关于直线 $y=x$ 对称得到

反向树状数组

对于维护大于某个数的区间，可以通过反向树状数组来做
传统的树状数组，每个点维护的区间范围是 $\left.(i-lowbit(i),i\right.]$ ,而反向树状数组每个点维护的区间范围是 $\left.[i,i+lowbit(i)\right.)$

查询操作，每次 $i=i+lowbit(i)$
更新操作，每次 $i=i-lowbit(i)$
代码
贴一段例题的ac代码，中间包含模板

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e5 + 10;
struct EDGE
{
    int u, v, w;
    bool operator < (const EDGE &o)const
    {
        return w < o.w;
    }
} edge[maxn << 3];
int f[maxn], tot;
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void joint(int u, int v)
{
    int fu = find(u), fv = find(v);
    if (fu != fv)
        f[fu] = fv;
}

ll kurskal(int n)
{
    ll res = 0;
    for (int i = 0; i <= n; ++i)
        f[i] = i;
    sort(edge, edge + tot);
    for (int i = 0; i < tot; ++i)
    {
        if (find(edge[i].u) != find(edge[i].v))
        {
            joint(edge[i].u, edge[i].v);
            res += edge[i].w;
        }
    }
    return res;
}

struct POINT
{
    int x, y, id;
} point[maxn], temp[maxn];
struct BIT
{
    int _N;
    pii bit[maxn];
    void init(int n)
    {
        _N = n;
        for (int i = 1; i <= n; ++i)
        {
            bit[i] = pii(inf, -1);
        }
    }

    void update(int k,pii v)
    {
        for (; k > 0; k -= lowbit(k))
        {
            bit[k] = min(bit[k], v);
        }
    }

    pii query (int k)
    {
        pii res(inf, -1);
        for (; k <= _N; k += lowbit(k))
        {
            res = min(res, bit[k]);
        }
        return res;
    }
} bit;

int a[maxn], b[maxn];
void manhattan_mst(POINT p[], int n)
{
    for (int cas = 0; cas < 4; ++cas)
    {
        if (cas == 1 || cas == 3)
            for (int i = 0; i < n; ++i)
                swap(p[i].x, p[i].y);
        else if (cas == 2)
            for (int i = 0; i < n; ++i)
                p[i].x = -p[i].x;
        for (int i = 0; i < n; ++i)
        {
            b[i] = p[i].y - p[i].x;
        }
        sort(b, b + n);
        int m = unique(b, b + n) - b;
        sort(p, p + n, [](POINT a, POINT b) {
            return a.x > b.x;
        });
        bit.init(m);
        for (int i = 0; i < n; ++i)
        {
            int l = lower_bound(b, b + m, p[i].y - p[i].x) - b;
            pii res = bit.query(l + 1);
            if (res.second != -1)
                edge[tot++] = {p[i].id, res.second, res.first - p[i].x - p[i].y};
            bit.update(l + 1, pii(p[i].x + p[i].y, p[i].id));
        }
    }
}

int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                point[(i - 1) * m + j].id = (i - 1) * m + j;
                read(point[(i - 1) * m + j].x);
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                read(point[(i - 1) * m + j].y);
            }
        }
        tot = 0;
        for (int i = 1; i <= n; ++i)
        {
            int len = 0;
            for (int j = 1; j <= m; ++j)
            {
                temp[len++] = point[(i - 1) * m + j];
            }
            manhattan_mst(temp, len);
        }
        for (int j = 1; j <= m; ++j)
        {
            int len = 0;
            for (int i = 1; i <= n; ++i)
            {
                temp[len++] = point[(i - 1) * m + j];
            }
            manhattan_mst(temp, len);
        }
        printf("%lld\n", kurskal(n * m));
    }
}

图论-曼哈顿距离最小生成树

问题

定理

做法

分析

完善

反向树状数组

代码