跳转至

曼哈顿距离最值

两个 \(d\) 维的点 \((x_1,x_2,...,x_d)\) 和 \((y_1,y2,...,y_d)\) 的哈曼顿距离定义为 \(|x_1-y_1|+|x_2-y_2|+...+|x_d-y_d|\)

\(|x_1-x_2|+|y_1-y_2|=\max(|x_1^{'}-x_2^{'}|,|y_1^{'}-y_2^{'}|)\)

\(x_1^{'}=x_1+y_1,y_1^{'}=y_1-x_1\)

求二维平面上两点间最大的曼哈短距离 \(\max(max(x^{'})-\min(x^{'}),max(y^{'})-\min(y^{'}))\)

例题

P1648 看守 - 洛谷

二进制枚举每一维最终的正负号, 求的最终每一维的和的最大值与最小值

答案即为最大值与最小值之差

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
vector<int> a[1000005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    for (int i = 0 ; i < n ; i++) {
        a[i].resize(d);
        for (int j = 0 ; j < d ; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i = 0 ; i < 1 << d ; i++) {
        int mx = 0x7fffffff + 1, mi = 0x7fffffff;
        for (int j = 0 ; j < n ; j++) {
            int sum = 0;
            for (int k = 0 ; k < d ; k++) {
                if (i & 1 << k) {
                    sum += a[j][k];
                } else {
                    sum -= a[j][k];
                }
            }
            mx = max(mx, sum);
            mi = min(mi, sum);
        }
        ans = max(ans, mx - mi);
    }
    cout << ans << "\n";
    return 0;
}

Problem - G - Codeforces

二进制枚举绝对值符号, 用线段树维护区间max

答案为 max(f[i]+f[(~i) & ((1 << k) - 1)])

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
int k;
struct Info {
    int L, R;
    array<int, 32> f;
    Info() {
        f = array<int, 32>{};
    }
    void init(int tL, int tR, array<int, 32> v) { // build 内初始化
        L = tL;
        R = tR;
        for (int i = 0 ; i < 1 << k ; i++) {
            f[i] = 0;
            for (int j = 0 ; j < k ; j++) {
                if (i & 1 << j) {
                    f[i] += v[j];
                } else {
                    f[i] -= v[j];
                }
            }
        }
    }
    friend Info operator+(const Info &lhs, const Info &rhs) { // pushup
        Info res;
        res.L = lhs.L;
        res.R = rhs.R;
        for (int i = 0 ; i < 1 << k ; i++) {
            res.f[i] = max(lhs.f[i], rhs.f[i]);
        }
        return res;
    }
};
array<int, 32> a[200005];
struct SegmentTree {
    int N = 0;
    vector<Info> tr;
    SegmentTree(int n) {
        init(n);
    }
    void clear() {
        N = 0;
        tr.resize(0);
    }
    void init(int n) {
        N = n;
        n <<= 2;
        tr.resize(n);
    }
    void build() {
        build(1, N);
    }
    void build(int L, int R, int p = 1) {
        if (L == R) {
            tr[p].init(L, R, a[L]);
            return;
        }
        int mid = L + R >> 1;
        build(L, mid, p << 1);
        build(mid + 1, R, p << 1 | 1);
        tr[p] = tr[p << 1] + tr[p << 1 | 1];
    }
    void modify(int QL, int QR, int p = 1) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            tr[p].init(QL, QR, a[QL]);
            return;
        }
        int mid = tr[p].L + tr[p].R >> 1;
        if (QL <= mid) modify(QL, QR, p << 1);
        if (QR >= mid + 1) modify(QL, QR, p << 1 | 1);
        tr[p] = tr[p << 1] + tr[p << 1 | 1];
    }
    Info query(int QL, int QR, int p = 1) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            return tr[p];
        }
        int mid = tr[p].L + tr[p].R >> 1;
        if (QR <= mid) return query(QL, QR, p << 1);
        else if (QL >= mid + 1) return query(QL, QR, p << 1 | 1);
        return query(QL, QR, p << 1) + query(QL, QR, p << 1 | 1);
    }
}; // SegmentTree
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j < k ; j++) {
            cin >> a[i][j];
        }
    }
    SegmentTree st(n);
    st.build();
    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int pos;
            cin >> pos;
            for (int i = 0 ; i < k ; i++) {
                cin >> a[pos][i];
            }
            st.modify(pos, pos);
        } else {
            int L, R;
            cin >> L >> R;
            auto res = st.query(L, R);
            int ans = 0;
            for (int i = 0 ; i < 1 << k ; i++) {
                ans = max(ans, res.f[i] + res.f[(~i) & ((1 << k) - 1)]);
            }
            cout << ans << "\n";
        }
    }
    return 0;
}