---
tags: VNOJ, Free Contest, Math, Data Structure, Transformation, Implementation, SPyofgame, hhoangcpascal
title: 🌱 Free Contest 131 - DISPOINT
author: Editorial-Slayers Team
license: Public domain
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🌱 Free Contest 131 - DISPOINT}$

-----

###### 🔗 Link: [https://oj.vnoi.info/problem/fc131_dispoint](https://oj.vnoi.info/problem/fc131_dispoint)
###### 📌 Tags: `Math`, `Transformation`, `Implementation`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: @hhoangcpascal , [@mạnh](https://codeforces.com/profile/Hoa_Dau_Biec), [@dantalion](), @Melonade
###### 📋 Content:

[TOC]

-----
## Hướng dẫn

Đặt $f(p, a, b) = max\left(a \times (x_p - x_q) + b \times (y_p - y_q)\ \bigg| \ q = 1 \dots p\right)$

Ta có $(|x_p - x_q| + |y_p - y_q|) = max \left(\pm (x_p - x_q)\pm (y_p - y_q) \right)$

Nên với mọi $p = 1 \dots n$ ta có $max(|x_p - x_q| + |y_p - y_q|) = max(A, B, C, D)$ với $\begin{cases}
A = max(+(x_p - x_q) + (y_p - y_q)) = f(p, +1, +1)\\
B = max(-(x_p - x_q) + (y_p - y_q)) = f(p, -1, +1)\\
C = max(+(x_p - x_q) - (y_p - y_q)) = f(p, +1, -1)\\
D = max(-(x_p - x_q) - (y_p - y_q)) = f(p, -1, -1)\\
\end{cases}$

Để tính $f(p, a, b)$ ta có thể gán $\begin{cases}
x_i := x_i \times a\\
y_i := y_i \times b\\
\end{cases}$ trước, sau đó hàm $f(p)$ giờ có thể tính như sau:

- Ta sắp xếp $(x_i, y_i)$ theo $x_i$ tăng dần rồi ưu tiên $y_i$ tăng dần
- $f(p) = max\left((x_p + y_p) - (x_q + y_q)\ \bigg| \ q = 1 \dots p\right) = (x_p + y_p) - min\left(x_q + y_q\ \bigg| \ q = 1 \dots p\right)$
- Để tính phần $min()$ đó chúng ta có thể sử dụng cấu trúc dữ liệu dạng cây trong $O(\log p)$ cập nhật và tính kết quả

-----
## Tối ưu

Thay vì sài cây, đặt $g(q) = min\left(x_q + y_q\ \bigg| \ q = 1 \dots p\right) = min \Large(\normalsize (x_q + y_q), g(q - 1) \Large) \normalsize$

Lúc này ta có $f(p) = (x_p + x_q) - g(p - 1)$ được tính trong $O(1)$ với $O(n)$ tiền xử lí

Tuy đã bỏ được phần $O(\log)$ trong việc sài cấu trúc dữ liệu, lúc này chúng ta vẫn chưa bỏ được hàm sắp xếp

Rút gọn công thức, với mọi $p = 1 \dots n$, ta có $max(|x_p - x_q| + |y_p - y_q|) = max(A, B, C, D)$ với $\begin{cases}
A = f(p, +1, +1) = (x_p + y_p) - min(x_q + y_q)\\
B = f(p, -1, +1) = max(x_q - y_q) - (x_p - y_p)\\
C = f(p, +1, -1) = (x_p - y_p) - min(x_q - y_q)\\
D = f(p, -1, -1) = max(x_q + y_q) - (x_p + y_p)\\
\end{cases}$

Đặt $\begin{cases}
s_i = x_i + y_i\\
d_i = x_i - y_i\\
\end{cases}$ ta dễ dàng tiền xử lí được $\begin{cases}
max(s)\\
min(s)\\
max(d)\\
min(d)\\
\end{cases}$ do đó có thể xử lí truy vấn trong $O(1)$

-----
### Code

> **Time:** $O(n \log n)$
> **Space:** $O(n)$
> **Algo:** Transformation, Math, Data Structure, Sorting

:::success
:::spoiler hhoangcpascal - Tree Implementation

/// hhoangcpascal

#include <iostream>
#include <algorithm>
#define llong long long

using namespace std;

struct Point {
    int x, y, pos;

    bool operator < (const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
} P[200006];

int sorted[200006], bit[200006], sz;
int n, ans[200006];

void Update(int u, int val) {
    for(; u <= sz; u += (u & (-u))) bit[u] = min(bit[u], val);
}

int Query(int u) {
    int mmin = 1e9;
    for(; u > 0; u -= (u & (-u))) mmin = min(mmin, bit[u]);
    return mmin;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> P[i].x;
    for(int i = 1; i <= n; ++i) cin >> P[i].y;
    for(int i = 1; i <= n; ++i) P[i].pos = i;

    for(int s = 1; s <= 4; ++s) {
        for(int i = 1; i <= n; ++i) {
            if (s == 2 || s == 4) P[i].y = -P[i].y;
            else if (s == 3) P[i].x = -P[i].x;
        }

        sort(P+1, P+n+1);

        sz = 0;
        for(int i = 1; i <= n; ++i) sorted[++sz] = P[i].y;

        sort(sorted+1, sorted+sz+1);
        sz = unique(sorted+1, sorted+sz+1) - sorted - 1;

        for(int i = 1; i <= sz; ++i) bit[i] = 1e9;

        for(int i = 1; i <= n; ++i) {
            int y = lower_bound(sorted + 1, sorted + sz + 1, P[i].y) - sorted;

            ans[P[i].pos] = max(ans[P[i].pos], P[i].x + P[i].y - Query(y));
            Update(y, P[i].x + P[i].y);
        }
    }

    for(int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    return 0;
}

:::

:::success
:::spoiler SPyofgame - Tree Implementation

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int LIM = 2e5 + 25;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

struct Point 
{
    int x, y, p;
    Point (int x = 0, int y = 0, int p = 0)
    : x(x), y(y), p(p) {}
};

bool operator < (const Point &a, const Point &b)
{
    return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int t[LIM];
int tsz = 0;
void init(int n)
{
    tsz = n;
    memset(t, +INF, sizeof(t[0]) * (tsz + 1));
}

void update(int p, int v)
{
    for (; p <= tsz; p += p & -p)
        minimize(t[p], v);
}

int query(int p)
{
    int res = +INF;
    for (; p >= 1; p -= p & -p)
        minimize(res, t[p]);

    return res;
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int n;
Point a[LIM];
int yset[LIM];
int res[LIM];

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) a[i].p = i;   
    for (int i = 1; i <= n; ++i) res[i] = 0;

    for (int rotation = 1; rotation <= 4; ++rotation)
    {
        if (rotation == 2) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        if (rotation == 3) for (int i = 1; i <= n; ++i) a[i].x = -a[i].x;
        if (rotation == 4) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;

        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) yset[i] = a[i].y;
        sort(yset + 1, yset + n + 1);
        int ysize = unique(yset + 1, yset + n + 1) - (yset + 1);

        init(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            int y = lower_bound(yset + 1, yset + n + 1, a[i].y) - yset;
            maximize(res[a[i].p], a[i].x + a[i].y - query(y));
            update(y, a[i].x + a[i].y);
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << " ";

    return 0;
}

:::

> **Time:** $O(n \log n)$
> **Space:** $O(n)$
> **Algo:** Transformation, Math, Sorting
> [color=lightgreen]

:::success
:::spoiler Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int LIM = 2e5 + 25;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

struct Point 
{
    int x, y, p;
    Point (int x = 0, int y = 0, int p = 0)
    : x(x), y(y), p(p) {}
};

bool operator < (const Point &a, const Point &b)
{
    return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int n;
Point a[LIM];
int res[LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) a[i].p = i;   
    for (int i = 1; i <= n; ++i) res[i] = 0;

    for (int rotation = 1; rotation <= 4; ++rotation)
    {
        if (rotation == 2) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        if (rotation == 3) for (int i = 1; i <= n; ++i) a[i].x = -a[i].x;
        if (rotation == 4) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        sort(a + 1, a + n + 1);
        
        int g = a[1].x + a[1].y;
        for (int i = 2; i <= n; ++i)
        {
            maximize(res[a[i].p], a[i].x + a[i].y - g);
            minimize(g, a[i].x + a[i].y);
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << " ";

    return 0;
}

:::

> **Time:** $O(n)$
> **Space:** $O(n)$
> **Algo:** Transformation, Math, Implementation
> [color=lightgreen]

:::success
:::spoiler Code

#include <algorithm>
#include <iostream>

using namespace std;

const int LIM = 2e5 + 25;

int n;
int x[LIM];
int y[LIM];
int Sum[LIM];
int Dif[LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) cin >> y[i];

    for (int i = 1; i <= n; ++i)
    {
        Sum[i] = x[i] + y[i];
        Dif[i] = x[i] - y[i];
    }

    int maxSum = *max_element(Sum + 1, Sum + n + 1);
    int minSum = *min_element(Sum + 1, Sum + n + 1);
    int maxDif = *max_element(Dif + 1, Dif + n + 1);
    int minDif = *min_element(Dif + 1, Dif + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int desSum = max(maxSum - Sum[i], Sum[i] - minSum);
        int desDif = max(maxDif - Dif[i], Dif[i] - minDif);
        cout << max(desSum, desDif) << " ";
    }

    return 0;
}

:::

-----
### Bonus

- Với trường hợp cho $q$ truy vấn $(x_0, y_0)$ và tìm đường đi taxicab xa nhất tới một điêm trong $n$ điểm cho trước thì bạn làm được không ?