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

日付: 12月 16, 2018

[Problem - 1093G - Codeforces](https://codeforces.com/contest/1093/problem/G)
## Problem
Given <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k-dimensional points (with modification), answer queries of calculating the maximum manhattan distance between two points in range <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r].

## Solution
For two 2-dimensional points <math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_1, y_1)</annotation></semantics></math>(x1,y1) and <math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_2, y_2)</annotation></semantics></math>(x2,y2), their manhattan is the maximum of 4 cases: <math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo>+</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo><mo>−</mo><mo>(</mo><msub><mi>x</mi><mn>2</mn></msub><mo>+</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_1+y_1) - (x_2+y_2)</annotation></semantics></math>(x1+y1)−(x2+y2), <math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo>−</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo><mo>−</mo><mo>(</mo><msub><mi>x</mi><mn>2</mn></msub><mo>−</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_1-y_1)-(x_2-y_2)</annotation></semantics></math>(x1−y1)−(x2−y2), <math><semantics><mrow><mo>(</mo><mo>−</mo><msub><mi>x</mi><mn>1</mn></msub><mo>+</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo><mo>−</mo><mo>(</mo><mo>−</mo><msub><mi>x</mi><mn>2</mn></msub><mo>+</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(-x_1+y_1)-(-x_2+y_2)</annotation></semantics></math>(−x1+y1)−(−x2+y2), <math><semantics><mrow><mo>(</mo><mo>−</mo><msub><mi>x</mi><mn>1</mn></msub><mo>−</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo><mo>−</mo><mo>(</mo><mo>−</mo><msub><mi>x</mi><mn>2</mn></msub><mo>−</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(-x_1-y_2)-(-x_2-y_2)</annotation></semantics></math>(−x1−y2)−(−x2−y2). We can maintain a minimum and a maximum segment tree for each case, and the maximum manhattan distance in range <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r] is the maximum of the maximum minus minimum value in <math><semantics><mrow><mo>[</mo><mi>l</mi><mo separator="true">,</mo><mi>r</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[l,r]</annotation></semantics></math>[l,r] for each segment tree. 
For <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>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)

コメント

コメントを投稿