DDOSvoid's Blog

CF 1093G Multidimensional Queries

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/1093/G

简要题意：给定 $n$ 个在 $k$ 维空间的整点 $a_i$，两点的距离为 $k$ 维空间的曼哈顿距离，即 $\sum_{i=1}^k|a_{x,i}-a_{y,i}|$，现在有 $m$ 次操作，操作由两种：给定 $x$ 和一个新的坐标 $b$，令 $a_x=b$；给定区间 $[l,r]$，求区间 $[l,r]$ 内距离最远的两个点的距离

$n,m\le 2\times 10^5, k\le 5$，时间限制 $6$ 秒

Solution

我们考虑将曼哈顿距离的绝对值拆出来

由于答案只需要求最大值，我们直接枚举每个数的符号，注意到只有满足正确符号的两个距离才有可能凑成最大值

所以我们直接那线段树维护 $2^k$ 个状态的最大值即可

时间复杂度 $O(2^kn\log n)$

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
#include <iostream>
#define maxn 200010
#define maxm 5
#define INF 1000000000
#define ll long long
using namespace std;

int n, k, M, q, a[maxn][maxm], b[maxn][1 << maxm];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    int v[32]; 
} T[maxn * 4], _;
inline Seg maintain(const Seg &ls, const Seg &rs) {
    Seg o;
    for (int i = 0; i <= M; ++i) o.v[i] = max(ls.v[i], rs.v[i]);
    return o; 
}

void build(int i, int l, int r) {
    if (l == r) {
        for (int o = 0; o <= M; ++o)
            T[i].v[o] = b[l][o];
        return ; 
    }
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    T[i] = maintain(T[lc], T[rc]); 
} 

void update(int i, int l, int r, int k, int *v) {
    if (l == r) {
        for (int o = 0; o <= M; ++o) T[i].v[o] = v[o];
        return ;
    } int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, v);
    else update(rc, m + 1, r, k, v); 
    T[i] = maintain(T[lc], T[rc]); 
}

Seg query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return _;
    if (L <= l && r <= R) return T[i];
    int m = l + r >> 1;
    return maintain(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
}

inline void solve_1() {
    int x, a[maxm], b[1 << maxm] = { 0 }; cin >> x; 
    for (int i = 0; i < k; ++i) cin >> a[i];
    for (int S = 0; S <= M; ++S) 
        for (int i = 0; i < k; ++i)
            if (S >> i & 1) b[S] += a[i];
            else b[S] -= a[i];
    update(1, 1, n, x, b); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    Seg t = query(1, 1, n, x, y);
    int ans = -INF;
    for (int i = 0; i <= M; ++i)
        ans = max(ans, t.v[i] + t.v[M ^ i]);
    cout << ans << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; M = (1 << k) - 1;
    for (int i = 0; i <= M; ++i) _.v[i] = -INF;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < k; ++j) cin >> a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int S = 0; S <= M; ++S)
            for (int o = 0; o < k; ++o)
                if (S >> o & 1) b[i][S] += a[i][o];
                else b[i][S] -= a[i][o];
    cin >> q; build(1, 1, n); 
    for (int i = 1; i <= q; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    } 
    return 0;
}