Codeforces - Multidimensional Queries

Source: Educational Codeforces Round 56: G. Multidimensional Queries
Tags: Data Structures

Problem:
Cho N điểm trong hệ không gian K chiều, gọi khoảng cách giữa hai điểm A[x] và A[y] là
𝚺(i = 1..K) |A[x][i] - A[y][i]| (cũng được biết đến với tên khoảng cách Manhattan).
Bạn cần thực hiện Q truy vấn thuộc 1 trong 2 loại:
1 i b[1] b[2]... b[K]: Đặt lại tọa độ điểm A[i] thành (b[1], b[2], ..., b[K]);
2 L R: Tìm khoảng cách lớn nhất giữa hai điểm A[i] và A[j] thỏa L ≤ i, j ≤ R.
Dòng đầu là N, K. Dòng i trong N dòng tiếp theo chứa K số A[i][1], A[i][2], ..., A[i][K].
Dòng sau là Q. Q dòng sau thể hiện Q truy vấn thuộc 1 trong 2 loại trên.
1 ≤ N ≤ 2e5. 1 ≤ K ≤ 5.
-1e6 ≤ A[i][j] ≤ 1e6.
1 ≤ Q ≤ 2e5.

Ví dụ:
Input:
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5

Output:

8

4

4

12

10

Explanation:

Truy vấn 2 1 5: Khoảng cách lớn nhất là khoảng cách giữa điểm 1 và 5

Truy vấn 2 1 3: Khoảng cách lớn nhất là khoảng cách giữa điểm 1 và 3

Truy vấn 2 3 5: Khoảng cách lớn nhất là khoảng cách giữa điểm 3 và 5

Truy vấn 1 5 -1 -2: Đặt lại điểm 5 thành tọa độ (-1, -2)

Truy vấn 2 1 5: Khoảng cách lớn nhất là khoảng cách giữa điểm 4 và 5

Truy vấn 1 4 -1 -2: Đặt lại điểm 4 thành tọa độ (-1, -2)

Truy vấn 2 1 5: Khoảng cách lớn nhất là khoảng cách giữa điểm 3 và 4

Solution:

Có thể thấy ngay là ta sẽ cần sử dụng đến Interval Tree, nhưng vấn đề là cập nhật như thế nào. Chúng ta sẽ cần biến đổi công thức đôi chút. Khoảng cách giữa điểm A[x] và A[y]:

   𝚺(i = 1..K) |A[x][i] - A[y][i]|

= 𝚺(i = 1..K) k[i] * (A[x][i] - A[y][i])

= 𝚺(i = 1..K) k[i] * A[x][i] - k[i] * A[y][i]

Trong đó k[i] = 1 nếu A[x][i] ≥ A[y][i] và k[i] = -1 nếu A[x][i] < A[y][i].

Để ý rằng, việc đảo dấu k[i] bất kỳ (đổi k[i] = -k[i]) sẽ không làm biểu thức tăng giá trị lên mà chỉ có thể giảm xuống, do đó, giữa hai điểm A[x] và A[y] tuy chưa biết bộ k[i] của chúng ta như thế nào nhưng ta có thể thử tất cả trường hợp, max kết quả trong tất cả trường hợp chính là khoảng cách cần tìm. Lúc này ta có thể dựng 2 ^ K cây IT để tìm kết quả tương ứng, chi tiết xem thêm code ở dưới.

Độ phức tạp: O((Q + N) * 2^k * logN)

Code:

#include <iostream>

#include <vector>

using namespace std;

int n, k, IT[1000000][32];

void update(int x, vector <int> p, int i, int l, int r) {

    if (x < l || r < x) return;

    if (l == r) {

        for (int m = 0; m < (1 << k); ++m) {

            int calc = 0;

            for (int i = 0; i < k; ++i)

                (m & (1 << i)) ? calc += p[i] : calc -= p[i];

            IT[i][m] = calc;

        }

        return;

    }

    update(x, p, 2 * i, l, (l + r) / 2);

    update(x, p, 2 * i + 1, (l + r) / 2 + 1, r);

    for (int m = 0; m < (1 << k); ++m)

        IT[i][m] = max(IT[2 * i][m], IT[2 * i + 1][m]);

}

int get(int x, int y, int m, int i, int l, int r) {

    if (y < l || r < x) return -1e9;

    if (x <= l && r <= y) return IT[i][m];

    int x1 = get(x, y, m, 2 * i, l, (l + r) / 2);

    int x2 = get(x, y, m, 2 * i + 1, (l + r) / 2 + 1, r);

    return max(x1, x2);

}

int ans(int l, int r) {

    int res = 0;

    for (int m = 0, x1, x2; m < (1 << k); ++m)

        x1 = get(l, r, m, 1, 1, n),

        x2 = get(l, r, ((1 << k) - 1) ^ m, 1, 1, n),

        res = max(res, x1 + x2);

    return res;

}

int main() {

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i) {

        vector <int> p;

        for (int i = 0, x; i < k; ++i)

            cin >> x, p.push_back(x);

        update(i, p, 1, 1, n);

        p.clear();

    }

    int q; cin >> q;

    for (int t, i, l, r; q--;) {

        cin >> t;

        if (t == 1) {

            cin >> i;

            vector <int> p;

            for (int i = 0, x; i < k; ++i)

                cin >> x, p.push_back(x);

            update(i, p, 1, 1, n);

            p.clear();

        }

        else

            cin >> l >> r,

            cout << ans(l, r) << '\n';

    }

}