Chênh Lệch Lớn Nhất
Đề bài
Cho hai dãy số $A$ và $B$, cả hai đều có $n$ phần tử và đã được sắp xếp tăng dần. Cần tạo ra một dãy số $C$ gồm $m$ phần tử sao cho:
- Dãy $C$ là dãy tăng dần.
- Tồn tại một giá trị $p$ $(1 \le p < m)$, sao cho: $p$ phần tử đầu tiên của $C$ là một dãy con liên tiếp của $A$ và $(m - p)$ phần tử cuối của $C$ là một dãy con liên tiếp của $B$.
Gọi $D$ là dãy số chứa $m - 1$ giá trị chênh lệch tuyệt đối giữa hai phần tử liên tiếp trong $C$: $D[i] = |C[i+1] - C[i]|$ với $1 \le i \le m - 1$. Hãy tìm giá trị lớn nhất trong dãy $D$.
Dữ liệu:
- Dòng 1: chứa hai số nguyên $n$ và $m$ $(1 \le n \le 300\,000,\ 2 \le m \le 2 \times n)$;
- Dòng 2: chứa $n$ số nguyên được sắp xếp tăng dần $A_1, A_2, \dots, A_n$ $(0 < A_i \le 2 \cdot 10^9;\ \forall i = 1 \dots n)$;
- Dòng 3: chứa $n$ số nguyên được sắp xếp tăng dần $B_1, B_2, \dots, B_n$ $(0 < B_i \le 2 \cdot 10^9;\ \forall i = 1 \dots n)$.
Kết quả: In ra một số nguyên duy nhất, là giá trị lớn nhất trong dãy $D$. Nếu không có cách nào tạo ra mảng $C$ thì in ra số $0$.
Ràng buộc:
| Subtask | Ràng buộc bổ sung | Điểm |
|---|---|---|
| 1 | $n \le 50$ | 20 |
| 2 | $n \le 200$ | 20 |
| 3 | $n \le 2\,000$ | 20 |
| 4 | Không có ràng buộc bổ sung | 40 |
3 4
2 6 7
3 8 95Giải thích ví dụ: có thể tạo dãy $C$ như sau: $[2, 3, 8, 9]$. Dãy $D$ tương ứng sẽ là $[1, 5, 1]$. Giá trị lớn nhất là $5$.
Đoạn của $A$ là $[2]$ (tím, $p = 1$), đoạn của $B$ là $[3, 8, 9]$ (xanh). Chỗ nối $2 < 3$ nên $C$ tăng dần. Giá trị lớn nhất $5 = 8 - 3$ nằm trong đoạn $B$.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngDãy C = một đoạn của A nối với một đoạn của B
Đọc kỹ đề thì dãy $C$ luôn có dạng: một đoạn liên tiếp của $A$ (dài $p$) ghép ngay sau đó là một đoạn liên tiếp của $B$ (dài $m - p$). Vì $A$, $B$ đã tăng dần sẵn nên bên trong mỗi đoạn đã tăng rồi, điều kiện "$C$ tăng dần" chỉ còn phải kiểm tra đúng 1 chỗ: chỗ nối, tức phần tử cuối của đoạn $A$ phải nhỏ hơn phần tử đầu của đoạn $B$.
Còn dãy $D$ gồm các chênh lệch liền kề trong $C$, nên mỗi giá trị của $D$ rơi vào đúng 1 trong 3 loại:
- Nằm trong đoạn A: $|a[k] - a[k-1]|$ của 2 phần tử liền kề thuộc đoạn lấy từ $A$.
- Nằm trong đoạn B: $|b[k] - b[k-1]|$ của 2 phần tử liền kề thuộc đoạn lấy từ $B$.
- Ở chỗ nối: $|b[u] - a[j]|$ với $a[j]$ là phần tử cuối của đoạn $A$, $b[u]$ là phần tử đầu của đoạn $B$.
Cả 4 subtask bên dưới đều xoay quanh 3 loại này, chỉ khác nhau ở chỗ duyệt nhanh hay chậm. Em nhập 2 dãy và $m$ rồi bấm Tiếp để xem lần lượt mọi cách tạo dãy $C$ hợp lệ, dãy $D$ của nó và giá trị lớn nhất rơi vào loại nào:
Subtask 1Duyệt trâu 4 vòng lặp – O(N⁴)
Duyệt trâu các khả năng ghép đoạn có thể xảy ra. Ta sẽ for $i$ là chỉ số của vị trí bắt đầu bên dãy con liên tiếp của $A$, sau đó for $j$ là chỉ số của vị trí kết thúc bên dãy con liên tiếp của $A$, tiếp theo trong đó ta sẽ for $u$ là chỉ số bắt đầu của dãy con liên tiếp $B$ và for tiếp $v$ là chỉ số kết thúc của dãy con liên tiếp $B$.
Lúc for phân đoạn của dãy $A$, ta có thể vừa tăng $j$ vừa tính mxA (chênh lệch lớn nhất giữa hai phần tử liền kề nằm trong đoạn con liên tiếp của $A$). Tương tự với $B$, ta cũng sẽ vừa tăng $v$ vừa tính mxB. Khi đấy, ta chỉ cần tính thêm chênh lệch giữa phần tử cuối của phân đoạn $A$ và phần tử đầu của phân đoạn $B$ là abs(b[u] - a[j]), kết hợp max với mxB, mxA là được chênh lệch lớn nhất của các phần tử trong mảng $C$.
a[j] < b[u] thì mới tính vào kết quả (để dãy $C$ tăng dần), và tổng độ dài 2 đoạn $(j - i + 1) + (v - u + 1)$ phải đúng bằng $m$.Code Subtask 1 – O(N⁴)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[300005], b[300005];
namespace sub1{
int solve(){
int res = 0;
for (int i = 1; i <= n; i ++){
int mxA = 0;
for (int j = i; j <= n; j ++){
if (j != i) mxA = max(mxA, abs(a[j] - a[j - 1]));
for (int u = 1; u <= n; u ++){
int mxB = 0;
for (int v = u; v <= n; v ++){
if (v != u) mxB = max(mxB, abs(b[v] - b[v - 1]));
if ((v - u + 1 + (j - i + 1)) == m && a[j] < b[u]){
res = max({res, mxB, mxA, abs(a[j] - b[u])});
}
}
}
}
}
return res;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= n; i ++){
cin >> b[i];
}
cout << sub1::solve() << endl;
}import sys
input = sys.stdin.readline
def solve_sub1(n, m, a, b):
res = 0
for i in range(n):
mxA = 0
for j in range(i, n):
if j != i:
mxA = max(mxA, abs(a[j] - a[j - 1]))
for u in range(n):
mxB = 0
for v in range(u, n):
if v != u:
mxB = max(mxB, abs(b[v] - b[v - 1]))
if (v - u + 1 + (j - i + 1)) == m and a[j] < b[u]:
res = max(res, mxB, mxA, abs(a[j] - b[u]))
return res
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve_sub1(n, m, a, b))Subtask 2Bớt 1 vòng lặp nhờ bảng mxA, mxB – O(N³)
Ta nhận xét rằng: nếu duyệt 3 vòng lồng nhau với 3 biến chạy, trong đó:
- $i$ là vị trí kết thúc của phân đoạn $A$;
- $u$ là vị trí bắt đầu của phân đoạn $B$;
- $j$ là vị trí bắt đầu của phân đoạn $A$, tức độ dài phân đoạn $A$ là $len = i - j + 1$.
Ta có thể dễ dàng suy ra được phân đoạn $B$ sẽ có độ dài là $m - len$ và có vị trí kết thúc là $u + (m - len) - 1$. Không cần vòng lặp thứ 4 nữa!
Khi đấy, việc ta cần xử lý là làm sao để tính nhanh được chênh lệch lớn nhất giữa các phần tử trong phân đoạn $A$ được chọn và trong phân đoạn $B$ được chọn. Ta gọi mxA[i][j] là độ chênh lệch lớn nhất của phân đoạn $A$ bắt đầu từ $i$ và kết thúc tại $j$. Ta sẽ có công thức truy hồi sau:
Tương tự ta cũng sẽ tạo được $mxB[i][j]$ cho dãy $B$.
Lưu ý: vẫn phải kết hợp xét điều kiện a[i] < b[u], độ dài đoạn $A$ phải nhỏ hơn $m$ (để đoạn $B$ có ít nhất 1 phần tử) và vị trí kết thúc của đoạn $B$ không vượt quá $n$.
Code Subtask 2 – O(N³)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[300005], b[300005];
namespace sub2{
int mxA[205][205], mxB[205][205];
int solve(){
int res = 0;
for (int i = 1; i <= n; i ++){
mxA[i][i] = 0;
for (int j = i + 1; j <= n; j ++){
mxA[i][j] = max(mxA[i][j - 1], abs(a[j] - a[j - 1]));
}
}
for (int i = 1; i <= n; i ++){
mxB[i][i] = 0;
for (int j = i + 1; j <= n; j ++){
mxB[i][j] = max(mxB[i][j - 1], abs(b[j] - b[j - 1]));
}
}
for (int i = 1; i <= n; i ++){
for (int u = 1; u <= n; u ++){
for (int j = 1; j <= i; j ++){
if ((i - j + 1) < m && (u + m - (i - j + 1) - 1) <= n
&& a[i] < b[u]){
res = max({res, mxA[j][i],
mxB[u][u + m - (i - j + 1) - 1],
abs(a[i] - b[u])});
}
}
}
}
return res;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= n; i ++){
cin >> b[i];
}
cout << sub2::solve() << endl;
}import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
mxA = [[0] * 205 for _ in range(205)]
mxB = [[0] * 205 for _ in range(205)]
def solve_sub2():
res = 0
for i in range(1, n + 1):
mxA[i][i] = 0
for j in range(i + 1, n + 1):
mxA[i][j] = max(mxA[i][j - 1], abs(a[j] - a[j - 1]))
for i in range(1, n + 1):
mxB[i][i] = 0
for j in range(i + 1, n + 1):
mxB[i][j] = max(mxB[i][j - 1], abs(b[j] - b[j - 1]))
for i in range(1, n + 1):
for u in range(1, n + 1):
for j in range(1, i + 1):
if (i - j + 1) < m and (u + m - (i - j + 1) - 1) <= n and a[i] < b[u]:
res = max(res,
mxA[j][i],
mxB[u][u + m - (i - j + 1) - 1],
abs(a[i] - b[u]))
return res
print(solve_sub2())Subtask 3Tách 3 trường hợp, xét riêng từng loại – O(N²)
Ta có thể chia dãy $D$ vào trong các trường hợp sau:
- Trường hợp 1: phần tử $D$ lớn nhất là trị tuyệt đối của hai phần tử trong mảng $A$.
- Trường hợp 2: phần tử $D$ lớn nhất là trị tuyệt đối của hai phần tử trong mảng $B$.
- Trường hợp 3: phần tử $D$ lớn nhất là trị tuyệt đối của phần tử cuối của dãy con liên tiếp từ mảng $A$ và phần tử đầu của dãy con liên tiếp từ mảng $B$.
Ta thấy rằng ta chỉ cần giá trị tối ưu, nên ta sẽ tính riêng max tối ưu cho từng trường hợp rồi max chúng lại với nhau.
Trường hợp 1
Duyệt hết các phân đoạn con $[i..j]$ có thể của mảng $A$. Khi đấy, ta sẽ lấy max trị tuyệt đối giữa hai phần tử liền kề. Sau đó ta sẽ xem xét thử rằng có khả năng tạo được một mảng $C$ gồm $m$ phần tử có sự xuất hiện của phân đoạn con này hay không.
Nhận xét rằng nếu muốn tạo được, thì ta sẽ gọi $l$ là vị trí nhỏ nhất sao cho $b[l] > a[j]$ ($j$ là vị trí cuối của phân đoạn con của $A$): đoạn $B$ chỉ được bắt đầu từ $l$ trở đi nên dài tối đa $n - l + 1$. Tạo được khi $(n - l + 1) + (j - i + 1) \ge m$ (và tất nhiên đoạn $A$ phải ngắn hơn $m$). Vì $a[j]$ tăng dần theo $j$ nên vị trí $l$ chỉ tiến lên, có thể duy trì bằng hai con trỏ.
Trường hợp 2
Tương tự với trường hợp 1: duyệt phân đoạn $[i..j]$ của $B$, gọi sus là vị trí lớn nhất mà $a[sus] < b[i]$, đoạn $A$ kết thúc tại sus dài tối đa sus phần tử, nên tạo được khi $sus + (j - i + 1) \ge m$.
Trường hợp 3
Duyệt hết tất cả vị trí $i$ của dãy $A$, sau đó xem xét chúng với từng phần tử $j$ của dãy $B$ rồi lấy max trị tuyệt đối, $O(N^2)$. Ở đây, ta phải xét xem thử là có khả năng tạo một dãy gồm $m$ phần tử nếu vị trí kết thúc là $i$ bên mảng $A$ và vị trí bắt đầu là $j$ bên mảng $B$ hay không. Việc này tương đương với việc $i + (n - j + 1)$ có lớn hơn hoặc bằng $m$ hay không, vì $i + (n - j + 1)$ là độ dài mảng $C$ tối đa mà có thể tạo được (kết hợp xét $a[i] < b[j]$).
if (m > 2)? Khi $m = 2$ thì $C$ chỉ có đúng 1 phần tử của $A$ và 1 phần tử của $B$, dãy $D$ chỉ có 1 giá trị là chỗ nối, nên không có trường hợp 1, 2. Và ở trường hợp 1, 2 code dùng a[j] - a[j - 1] không cần abs vì dãy đã tăng dần.Code Subtask 3 – O(N²)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[300005], b[300005];
namespace sub3{
int solve(){
int res = 0;
if (m > 2){
for (int i = 1; i <= n; i ++){
int mx = 0;
int l = 1;
for (int j = i + 1; j <= n; j ++){
mx = max(mx, a[j] - a[j - 1]);
while (l <= n and b[l] <= a[j]){
l ++;
}
if ((j - i + 1) < m && (n - l + 1) + (j - i + 1) >= m){
res = max(res, mx);
}
}
}
for (int i = 1; i <= n; i ++){
int mx = 0;
int sus = 0;
for (int j = 1; j <= n; j ++){
if (a[j] < b[i]) sus = max(sus, j);
}
for (int j = i + 1; j <= n; j ++){
mx = max(mx, b[j] - b[j - 1]);
if ((j - i + 1) < m && (sus) + (j - i + 1) >= m){
res = max(res, mx);
}
}
}
}
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= n; j ++){
if (i + (n - j + 1) >= m && a[i] < b[j])
res = max(res, abs(a[i] - b[j]));
}
}
return res;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= n; i ++){
cin >> b[i];
}
cout << sub3::solve() << endl;
}import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
def solve_sub3():
res = 0
if m > 2:
for i in range(1, n + 1):
mx = 0
l = 1
for j in range(i + 1, n + 1):
mx = max(mx, a[j] - a[j - 1])
while l <= n and b[l] <= a[j]:
l += 1
if (j - i + 1) < m and (n - l + 1) + (j - i + 1) >= m:
res = max(res, mx)
for i in range(1, n + 1):
mx = 0
sus = 0
for j in range(1, n + 1):
if a[j] < b[i]:
sus = max(sus, j)
for j in range(i + 1, n + 1):
mx = max(mx, b[j] - b[j - 1])
if (j - i + 1) < m and sus + (j - i + 1) >= m:
res = max(res, mx)
for i in range(1, n + 1):
for j in range(1, n + 1):
if i + (n - j + 1) >= m and a[i] < b[j]:
res = max(res, abs(a[i] - b[j]))
return res
print(solve_sub3())Subtask 4Hai con trỏ + Segment Tree – O(N log N)
Tương tự với subtask 3, nhưng ta sẽ xem xét tối ưu việc xử lý các trường hợp trong $O(N \log N)$.
Trường hợp 1
Nhận xét rằng, hai vị trí liền kề $i - 1, i$ của $A$ có khả năng cùng xuất hiện trong $C$ khi có một vị trí kết thúc $j \ge i$ sao cho đoạn $[i - 1..j]$ không quá $m - 1$ phần tử (không thể chọn quá $m - 1$ phần tử vào $C$), tức $j \le i + m - 3$. Vị trí $j$ này đồng thời phải thỏa mãn: với $l$ là vị trí nhỏ nhất sao cho $b[l] > a[j]$ thì
($\min(m - 1, j)$: chỉ có thể chọn không quá $m - 1$ và không quá $j$ phần tử có vị trí kết thúc là $j$ trong đoạn $A$; $\min(m - 1, n - l + 1)$: độ dài tối đa của đoạn $B$.)
Ta nhận thấy $val[j]$ có thể tính trước với mỗi $j$ (vẫn bằng hai con trỏ cho $l$). Sau đó đối với mỗi $i$, ta chỉ cần lấy max của $val$ trong khoảng $j \in [i,\ i + m - 3]$ rồi so với $m$. Truy vấn max trên đoạn thì dễ dàng xử lý bằng Segment Tree.
Trường hợp 2
Có thể xử lý tương tự vậy: $val[j]$ là độ dài tối đa khi đoạn $B$ bắt đầu tại $j$, bằng $\min(m - 1, n - j + 1)$ $+ \min(m - 1, l - 1)$ với $l$ là vị trí đầu tiên mà $a[l] \ge b[j]$ (các phần tử $a[1..l-1]$ đều nhỏ hơn $b[j]$). Cặp $b[i - 1], b[i]$ dùng được khi có vị trí bắt đầu $j$ với đoạn $[j..i]$ không quá $m - 1$ phần tử, tức $j \in [i - m + 2,\ i - 1]$.
Trường hợp 3
Giả sử ta đang xét vị trí thứ $i$ là vị trí kết thúc bên mảng $A$, ta có những nhận xét sau:
- Nếu ta chọn $b[u] > a[i]$ sao cho $|a[i] - b[u]|$ là tối đa nhất có thể, ta sẽ chọn $b[u]$ lớn nhất có thể để "mở rộng khoảng cách" giá trị giữa hai phần tử.
- Nếu ta chọn $b[u] = a[i]$ hoặc $b[u] < a[i]$ thì dãy $C$ không còn tăng dần, không hợp lệ.
Ở vị trí $i$, đoạn $A$ dài tối đa $len = \min(i, m - 1)$, đoạn $B$ dài ít nhất $m - len$, nên ta phải chọn $u$ sao cho $u + (m - len) - 1 \le n$, suy ra
Nếu ta có được $i$ ta có thể dễ dàng tính vị trí tối đa mà $u$ có thể đi tới. Tuy nhiên, chúng ta phải xét thêm rằng vị trí $u$ phải có điều kiện là $b[u] > a[i]$. Khi đấy, ta vẫn duy trì hai con trỏ để tính toán cập nhật vị trí $u$ nhỏ nhất (biến l trong code), đồng thời kết hợp với Segment Tree để thực hiện truy vấn lấy max, lấy min trên đoạn liên tiếp $[l,\ n - m + 1 + len]$ của $B$.
Code C++ thì Segment Tree cài đặt theo kiểu đệ quy: up gán giá trị 1 vị trí rồi cập nhật ngược lên các nút cha, re trả về max trên đoạn $[u, v]$ (trả về $-10^{18}$ nếu đoạn nút nằm ngoài), up_mn, re_mn tương tự cho min.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[300005], b[300005];
namespace sub4{
int premx[300005];
int premn[300005];
int mx[1200005];
int mn[1200005];
void reset(int x){
for (int i = 1; i <= x * 4; i ++){
mx[i] = 0;
}
}
void up(int x, int l, int r, int u, int chg){
if (l > r || l > u || r < u) return;
if (l == r){
mx[x] = chg;
return;
}
int mid = (l + r) / 2;
up(x * 2, l, mid, u, chg);
up(x * 2 + 1, mid + 1, r, u, chg);
mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
return;
}
int re(int x, int l, int r, int u, int v){
if (l > r || l > v || r < u) return -1e18;
if (l >= u && r <= v){
return mx[x];
}
int mid = (l + r) / 2;
return max(re(x * 2, l, mid, u, v), re(x * 2 + 1, mid + 1, r, u, v));
}
void up_mn(int x, int l, int r, int u, int chg){
if (l > r || l > u || r < u) return;
if (l == r){
mn[x] = chg;
return;
}
int mid = (l + r) / 2;
up_mn(x * 2, l, mid, u, chg);
up_mn(x * 2 + 1, mid + 1, r, u, chg);
mn[x] = min(mn[x * 2], mn[x * 2 + 1]);
return;
}
int re_mn(int x, int l, int r, int u, int v){
if (l > r || l > v || r < u) return 1e18;
if (l >= u && r <= v) return mn[x];
int mid = (l + r) / 2;
return min(re_mn(x * 2, l, mid, u, v), re_mn(x * 2 + 1, mid + 1, r, u, v));
}
int solve(){
int res = 0;
if (m > 2){
// case 1 : gia tri lon nhat cua D nam trong doan lien tiep A
int l = 1;
for (int i = 1; i <= n; i ++){
while (l <= n && b[l] <= a[i]){
l ++;
}
up(1, 1, n, i, min(m - 1, (n - l + 1)) + min(m - 1, i));
}
for (int i = 2; i <= n; i ++){
if ((re(1, 1, n, i, i + m - 3) ) >= m){
res = max(res, abs(a[i] - a[i - 1]));
}
}
reset(n);
l = 1;
for (int i = 1; i <= n; i ++){
while (l <= n && a[l] < b[i]) l ++;
up(1, 1, n, i, min(m - 1, n - i + 1) + min(m - 1, l - 1));
}
for (int i = 2; i <= n; i ++){
if (re(1, 1, n, i - m + 2, i - 1) >= m)res = max(res, abs(b[i] - b[i - 1]));
}
}
reset(n);
for (int i = 1; i <= n; i ++){
up(1, 1, n, i, b[i]);
}
for (int i = 1; i <= n; i ++){
up_mn(1, 1, n, i, b[i]);
}
// case 3: gias trij lon nhat cua D o vi tri dau cua B va vi tri cuoi cua A
int l = 1;
for (int i = 1; i <= n; i ++){
int len = min(i, m - 1);
while (l <= n && b[l] <= a[i]) l ++;
if (n - m + 1 + len >= 1 && l <= min(n, n - m + 1 + len)){
res = max({res, abs(re(1, 1, n, l, min(n, n - m + 1 + len)) - a[i]), abs(re_mn(1, 1, n, l, min(n, n - m + 1 + len)) - a[i])});
}
}
return res;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 1; i <= n; i ++){
cin >> b[i];
}
cout << sub4::solve() << endl;
}import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
INF = 10**18
size = 1
while size < n:
size <<= 1
mx = [-INF] * (2 * size)
mn = [INF] * (2 * size)
def build_max(arr):
for i in range(n):
mx[size + i] = arr[i + 1]
for i in range(size - 1, 0, -1):
mx[i] = max(mx[i << 1], mx[i << 1 | 1])
def build_min(arr):
for i in range(n):
mn[size + i] = arr[i + 1]
for i in range(size - 1, 0, -1):
mn[i] = min(mn[i << 1], mn[i << 1 | 1])
def update_max(pos, val):
i = size + pos - 1
mx[i] = val
i >>= 1
while i:
mx[i] = max(mx[i << 1], mx[i << 1 | 1])
i >>= 1
def update_min(pos, val):
i = size + pos - 1
mn[i] = val
i >>= 1
while i:
mn[i] = min(mn[i << 1], mn[i << 1 | 1])
i >>= 1
def query_max(l, r):
res = -INF
l += size - 1
r += size - 1
while l <= r:
if l & 1:
res = max(res, mx[l])
l += 1
if not (r & 1):
res = max(res, mx[r])
r -= 1
l >>= 1
r >>= 1
return res
def query_min(l, r):
res = INF
l += size - 1
r += size - 1
while l <= r:
if l & 1:
res = min(res, mn[l])
l += 1
if not (r & 1):
res = min(res, mn[r])
r -= 1
l >>= 1
r >>= 1
return res
def solve_sub4():
res = 0
if m > 2:
# case 1: D max in A
l = 1
for i in range(1, n + 1):
while l <= n and b[l] <= a[i]:
l += 1
update_max(i, min(m - 1, (n - l + 1)) + min(m - 1, i))
for i in range(2, n + 1):
if query_max(i, min(n, i + m - 3)) >= m:
res = max(res, abs(a[i] - a[i - 1]))
# reset
mx[:] = [-INF] * (2 * size)
l = 1
for i in range(1, n + 1):
while l <= n and a[l] < b[i]:
l += 1
update_max(i, min(m - 1, n - i + 1) + min(m - 1, l - 1))
for i in range(2, n + 1):
if query_max(max(1, i - m + 2), i - 1) >= m:
res = max(res, abs(b[i] - b[i - 1]))
# case 3: D max at ends
for i in range(1, n + 1):
update_max(i, b[i])
update_min(i, b[i])
l = 1
for i in range(1, n + 1):
length = min(i, m - 1)
while l <= n and b[l] <= a[i]:
l += 1
right = min(n, n - m + 1 + length)
if n - m + 1 + length >= 1 and l <= right:
res = max(res,
abs(query_max(l, right) - a[i]),
abs(query_min(l, right) - a[i]))
return res
print(solve_sub4())Lưu ý: Code C++ thì Segment Tree cài đặt theo kiểu đệ quy nên khi chuyển qua Python sẽ bị TLE. Ở code Python này cài đặt Segment Tree theo dạng mảng (từ dưới lên) để chạy nhanh hơn, còn lại mọi logic xử lý y như code C++.
[i - m + 3, i - 1], nhưng đoạn $B$ bắt đầu tại $j$ và chứa cả $b[i]$ thì dài $i - j + 1 \le m - 1$, tức $j \ge i - m + 2$. Thiếu mất 1 vị trí nên có test sai, ví dụ n = 2, m = 3, A = [4, 30], B = [11, 25]: đáp án là $14$ (dãy $C = [4, 11, 25]$) nhưng code cũ in $7$. Mình đã sửa thành i - m + 2 trong cả bản C++ lẫn Python (khung chạy tay bên dưới có sẵn test này).i - m + 2 ở subtask 4 như trên). Cả 8 bản đã được kiểm tra với 400 bộ test ngẫu nhiên ($n \le 8$, đủ mọi $m$ từ $2$ tới $2n$, có cả giá trị nhỏ dễ trùng nhau giữa $A$ và $B$ lẫn giá trị tới $2 \cdot 10^9$) so với chương trình vét cạn trực tiếp mọi cách chọn $(p,$ đoạn $A,$ đoạn $B)$: khớp 100%; bản subtask 4 còn được đối chiếu với subtask 3 trên 200 test $n = 40$. Thời gian với test lớn nhất từng subtask: subtask 1 ($n = 50$) 0.02 giây, subtask 2 ($n = 200$) 0.01 giây, subtask 3 ($n = 2000$) 0.03 giây, subtask 4 ($n = 300\,000$) khoảng 0.45 giây bản C++; các bản Python lần lượt khoảng 0.3 / 0.9 / 1.7 giây, riêng bản Python subtask 4 cần khoảng 8 giây với $n = 300\,000$ nên với Python các bạn nên nộp thử để xem giới hạn thời gian của hệ thống.
Nhận xét
Đăng nhận xét