owned this note
owned this note
Published
Linked with GitHub
---
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
```cpp=
/// 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
```cpp=
#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
```cpp=
#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
```cpp=
#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 ?