\(\Huge \text{🌱 Free Contest 131 - DISPOINT}\)

📌 Tags: Math, Transformation, Implementation
👤 Writer: @SPyofgame
👥 Contributor: @hhoangcpascal , @mạnh, @dantalion, @Melonade
📋 Content:

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

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;
}
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

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

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 ?
Select a repo