Codeforces 1093G. Multidimensional Queries (Manhattan Distance + Segment Tree)

日付: 12月 16, 2018

[Problem - 1093G - Codeforces](https://codeforces.com/contest/1093/problem/G)
## Problem
Given $n$ $k$-dimensional points (with modification), answer queries of calculating the maximum manhattan distance between two points in range $[l,r]$.

## Solution
For two 2-dimensional points $(x_1, y_1)$ and $(x_2, y_2)$, their manhattan is the maximum of  4 cases: $(x_1+y_1) - (x_2+y_2)$, $(x_1-y_1)-(x_2-y_2)$, $(-x_1+y_1)-(-x_2+y_2)$, $(-x_1-y_2)-(-x_2-y_2)$. We can maintain a minimum and a maximum segment tree for each case, and the maximum manhattan distance in range $[l,r]$ is the maximum of the maximum minus minimum value in $[l,r]$ for each segment tree. 
For $k$-dimension, just enumerate the bitmask.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)

template <class T> struct SingleST {
    const int n;
    vector<T> V;
    using Func = function<T(T, T)>;
    Func op, al;
    SingleST(const vector<T> &A, Func op = plus<T>(), Func al = plus<T>()
            ): n(A.size()), V(n * 2), op(op), al(al) {
        copy(A.begin(), A.end(), V.begin() + n);
        for (int i = n - 1; i > 0; i--) V[i] = op(V[i << 1], V[i << 1 | 1]);
    }
    void modify(int p, T val) {
        for (p += n, V[p] = al(V[p], val); p > 1; p >>= 1)
            V[p >> 1] = op(V[(p | 1) - 1], V[p | 1]);
    }
    T query(int l, int r) {
        assert(l < r);
        T left, right;
        bool b1 = false, b2 = false;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) left = b1 ? op(left, V[l++]) : V[l++], b1 = true;
            if (r & 1) right = b2 ? op(V[--r], right) : V[--r], b2 = true;
        }
        return !b1 ? right : !b2 ? left : op(left, right);
    }
};

const int N = 2e5 + 5;
int n, k;
vector<SingleST<int>> Min(35, SingleST<int>(vector<int>(N), [](int x, int y) { return min(x, y); },
[](int v, int d) { return d; }));
vector<SingleST<int>> Max(35, SingleST<int>(vector<int>(N), [](int x, int y) { return max(x, y); },
[](int v, int d) { return d; }));

int main() {
    scanf("%d%d", &n, &k);
    auto change = [&](int i) {
        vector<int> p(k);
        for (int j = 0; j < k; j++) scanf("%d", &p[j]);
        for (int s = 0; s < (1 << k); s++) {
            int sum = 0;
            for (int j = 0; j < k; j++) {
                sum += (s & 1 << j ? 1 : -1) * p[j];
            }
            Min[s].modify(i, sum);
            Max[s].modify(i, sum);
        }
    };
    FI(i, 1, n) change(i);
    int q;
    scanf("%d", &q);
    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int i;
            scanf("%d", &i);
            change(i);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = 0;
            for (int s = 0; s < (1 << k); s++) ans = max(ans, Max[s].query(l, r + 1) - Min[s].query(l, r + 1));
            printf("%d\n", ans);
        }
    }
}
```

KONGROOの基地

このブログを検索

Codeforces 1093G. Multidimensional Queries (Manhattan Distance + Segment Tree)

コメント

コメントを投稿