Collecting Numbers II (CSES 2217)
Đề bài
Collecting Numbers II – Gom các số II (CSES 2217)
Giới hạn thời gian: 1.00 giây. Giới hạn bộ nhớ: 512 MB.
Cho một mảng chứa mỗi số trong khoảng $1 \ldots n$ đúng một lần. Nhiệm vụ của bạn là gom các số từ $1$ đến $n$ theo thứ tự tăng dần.
Ở mỗi vòng, bạn đi qua mảng từ trái sang phải và gom được càng nhiều số càng tốt.
Cho $m$ thao tác, mỗi thao tác hoán đổi hai số trong mảng. Nhiệm vụ của bạn là cho biết số vòng cần đi sau mỗi thao tác.
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên $n$ và $m$: kích thước mảng và số thao tác.
- Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, \ldots, x_n$: các số trong mảng.
- Cuối cùng là $m$ dòng mô tả các thao tác. Mỗi dòng chứa hai số nguyên $a$ và $b$: hai số ở vị trí $a$ và $b$ được hoán đổi cho nhau.
Kết quả: In ra $m$ số nguyên: số vòng cần đi sau mỗi lần hoán đổi.
Ràng buộc:
- $1 \le n, m \le 2 \cdot 10^5$
- $1 \le a, b \le n$
CSES 2217 – Collecting Numbers II
Time limit: 1.00 s. Memory limit: 512 MB.
You are given an array that contains each number between $1 \ldots n$ exactly once. Your task is to collect the numbers from $1$ to $n$ in increasing order.
On each round, you go through the array from left to right and collect as many numbers as possible.
Given $m$ operations that swap two numbers in the array, your task is to report the number of rounds after each operation.
Input:
The first line has two integers $n$ and $m$: the array size and the number of operations.
The next line has $n$ integers $x_1,x_2,\ldots,x_n$: the numbers in the array.
Finally, there are $m$ lines that describe the operations. Each line has two integers $a$ and $b$: the numbers at positions $a$ and $b$ are swapped.
Output: Print $m$ integers: the number of rounds after each swap.
Constraints:
- $1 \le n, m \le 2 \cdot 10^5$
- $1 \le a,b \le n$
5 3
4 2 1 5 3
2 3
1 5
2 32
3
4Lờ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 😇.
Nhắc lại chuyện giới hạn thời gian: đề cho 1 giây thì toàn bài chỉ nên lặp cỡ $(3 \text{ đến } 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ (hên xui), vượt nữa là khả năng TLE rất cao (ngưỡng này cho C/C++, Python thì phải thấp hơn).
Bài này là version 2 của bài Collecting Numbers (CSES 2216). Các bạn phải làm được version 1 rồi mới qua version 2 nhé, vì bài viết này mình phát triển tiếp từ cách làm tối ưu của bài 1 (sắp xếp cặp (giá trị, vị trí), đếm số lần vị trí bị giảm). Bạn nào chưa làm thì xem bài giải Collecting Numbers trên blog trước nha.
Đề y như bài 1, chỉ thêm độ khó ở chỗ mảng không cố định mà bị hoán đổi giá trị tại 2 vị trí (tính từ 1, từ trái qua phải) $m$ lần. Giải thích ví dụ, mảng ban đầu là $4, 2, 1, 5, 3$:
- Đổi vị trí $2, 3$ ⇒ mảng $4, 1, 2, 5, 3$. Cần 2 lần đi: lần 1 gom $1, 2, 3$; lần 2 gom $4, 5$.
- Lưu ý là ta làm tiếp trên mảng vừa bị đổi chứ không phải mảng ban đầu. Đổi vị trí $1, 5$ ⇒ mảng $3, 1, 2, 5, 4$. Cần 3 lần đi: $1, 2$ | $3, 4$ | $5$.
- Đổi vị trí $2, 3$ ⇒ mảng $3, 2, 1, 5, 4$. Cần 4 lần đi: $1$ | $2$ | $3, 4$ | $5$.
Vì vậy kết quả in ra là $2, 3, 4$.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn lại sau mỗi lần đổi – O(m·n²)
Cách đơn giản nhất lúc nào cũng là vét cạn làm đúng theo đề, giống cách vét cạn đầu tiên của bài 1. Ta dùng lại đoạn code đó, gói thành hàm solve; mỗi lần đọc 2 vị trí thì hoán đổi rồi gọi lại solve để tính kết quả cho mảng mới.
a có đúng $n$ phần tử, chỉ số tính từ $0$; còn vị trí trong đề tính từ $1$. Nên đọc vào $x, y$ thì phải swap(a[x - 1], a[y - 1]) nhé các bạn.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int solve(int *a, int n) {
int res = 0, x = 1;
while (1) {
res++;
for (int i = 0; i < n; ++i) {
if (a[i] == x) {
x++;
if (x == n + 1) {
return res;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
while (m--) {
int x, y;
cin >> x >> y;
swap(a[x - 1], a[y - 1]);
cout << solve(a, n) << endl;
}
return 0;
}import sys
def solve(a, n):
res, x = 0, 1
while True:
res += 1
for v in a:
if v == x:
x += 1
if x == n + 1:
return res
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = list(map(int, data[2:n + 2]))
p = n + 2
out = []
for _ in range(m):
x, y = int(data[p]), int(data[p + 1])
p += 2
a[x - 1], a[y - 1] = a[y - 1], a[x - 1]
out.append(solve(a, n))
print('\n'.join(map(str, out)))
main()Cách này chắc chắn bị TLE: mỗi lần gọi solve xấu nhất đã là $O(n^2)$ như phân tích ở bài 1, mà còn gọi $m$ lần. Tuy vậy, khi chưa nghĩ ra cách tối ưu thì code vét cạn kiểu này rất đáng viết: chạy chậm, không nộp được, nhưng luôn cho kết quả đúng, nên ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu về sau (sinh test nhỏ ngẫu nhiên rồi so 2 kết quả).
Cách 2Chỉ xét các cặp kề bị ảnh hưởng – O((n + m) log n)
Nhắc lại cách tối ưu của bài 1
Đánh vị trí cho từng phần tử, sắp xếp các cặp tăng dần theo giá trị, khởi tạo res = 1; xét từ phần tử thứ 2, nếu vị trí (second) của nó nhỏ hơn vị trí của phần tử trước đó thì res++. Vì các giá trị chính là $1..n$ nên sau khi sắp, a[k].second chính là vị trí của số $k$ trong mảng.
Không cần duyệt lại cả dãy
Có thể các bạn nghĩ: mỗi lần đổi chỗ thì cập nhật lại vị trí 2 phần tử trong mảng đã sắp, rồi duyệt lại toàn bộ để đếm res. Nhưng như vậy mỗi lần đổi tốn $O(n)$, cả bài là $O(m \cdot n)$, với $m, n = 2 \cdot 10^5$ là $4 \cdot 10^{10}$ ⇒ vẫn TLE.
Mấu chốt để tối ưu: sau khi đổi chỗ 2 số ở vị trí $x, y$, chỉ có vị trí của 2 giá trị đó bị thay đổi. Gọi 2 giá trị đó (cũng là 2 chỉ số trong mảng đã sắp) là Min < Max. Điểm gãy chỉ có thể thay đổi ở các cặp kề có dính tới Min hoặc Max, tức là các cặp:
- $(Min - 1, Min)$ và $(Min, Min + 1)$,
- $(Max - 1, Max)$ và $(Max, Max + 1)$.
Các cặp còn lại không đổi gì nên không cần xét lại. Phải cẩn thận trường hợp Max - Min == 1 (2 giá trị liền nhau): khi đó $(Min, Min + 1)$ và $(Max - 1, Max)$ là cùng một cặp, chỉ được xét một lần. Còn khác 1 thì xét đủ 4 cặp.
Cách cập nhật res cho một cặp
Ví dụ xét cặp $(Min - 1, Min)$. Sau khi đổi, ở chỗ của Min sẽ là vị trí cũ của Max. Ta so sánh tình trạng trước và sau:
- Nếu trước đó
a[Min].second < a[Min - 1].second(đang là điểm gãy,resđã được++), mà giờ kiểm tra thấya[Max].second > a[Min - 1].second(sau khi đổi không còn gãy) thì phải trả lại:res--. - Ngược lại nếu trước đó không gãy, mà giờ thấy
a[Max].second < a[Min - 1].second(sau khi đổi lại gãy) thìres++.
Cứ theo quy luật đó xét tương tự với các cặp $(Max, Max + 1)$, $(Max - 1, Max)$, $(Min, Min + 1)$ để cập nhật res, sau đó in ra res.
res, phải đổi chỗ thật sự a[Min].second với a[Max].second để lần xét sau dựa trên tình trạng mảng mới nhất. Và cũng phải cập nhật lại map: mảng a và map luôn phải đồng bộ với nhau nhé các bạn.Tìm 2 giá trị đang nằm ở vị trí x, y
Đọc vào 2 vị trí $x, y$ (của mảng gần nhất trước đó), ta cần biết chúng ứng với chỉ số $i, j$ nào trong mảng đã sắp. Không thể tìm tuyến tính (lại $O(n)$ mỗi lần), mà phải tìm kiếm nhị phân: mình dùng cấu trúc map với key là a[i].second (vị trí) và value là chỉ số $i$ trong mảng hiện tại. Tìm trong map là tìm kiếm nhị phân nên mất $O(\log n)$. Có $i, j$ rồi thì lấy Min, Max và áp dụng quy luật ở trên.
Hai "lính canh" ở hai đầu
Khi Min = 1 thì cặp $(Min - 1, Min)$ đụng tới a[0]; khi Max = n thì cặp $(Max, Max + 1)$ đụng tới a[n + 1]. Để khỏi phải viết thêm if, ta đặt 2 lính canh: a[0].second = 0 (nhỏ hơn mọi vị trí nên số $1$ không bao giờ "gãy" với nó) và a[n + 1].second = n + 1 (lớn hơn mọi vị trí nên số $n$ không bao giờ "gãy" với nó).
a(n + 1) và có lính canh a[0] nhưng quên lính canh a[n + 1], nên khi Max = n thì a[Max + 1] truy cập ra ngoài vector (chạy với chế độ kiểm tra -D_GLIBCXX_DEBUG là báo lỗi ngay). Code dưới đây đã sửa bằng cách tạo a(n + 2) và gán a[n + 1] = {n + 1, n + 1} trước khi sắp xếp (nó là số lớn nhất nên sau khi sắp vẫn nằm cuối). Ngoài ra mình đổi endl thành "\n" vì in tới $2 \cdot 10^5$ dòng, mỗi endl đều ép đẩy bộ đệm ra màn hình khá tốn thời gian.Minh hoạ: chỉ các cặp kề bị ảnh hưởng mới thay đổi
Hàng thứ hai là mảng đã sắp theo giá trị: ô số $k$ ghi vị trí của số $k$. Giữa 2 ô liên tiếp, dấu ↩ là điểm gãy (vị trí giảm), dấu · là không gãy. Các cặp được tô tím là các cặp phải xét lại. Em nhập mảng và các thao tác (mỗi thao tác 2 số, cách nhau bởi dấu ;) rồi bấm Tiếp:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n + 2);
map<int, int> mp;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
a[n + 1].first = a[n + 1].second = n + 1;
sort(a.begin() + 1, a.end());
a[0].first = a[0].second = 0;
for (int i = 1; i <= n; ++i) {
mp[a[i].second] = i;
}
int res = 1;
for (int i = 1; i <= n; ++i) {
if (a[i].second < a[i - 1].second) {
res++;
}
}
while (m--) {
int x, y;
cin >> x >> y;
auto it1 = mp.find(x);
auto it2 = mp.find(y);
int i = it1->second;
int j = it2->second;
int Min = min(i, j);
int Max = max(i, j);
if (a[Min].second < a[Min - 1].second) {
if (a[Max].second > a[Min - 1].second) {
res--;
}
}
else {
if (a[Max].second < a[Min - 1].second) {
res++;
}
}
if (a[Max + 1].second < a[Max].second) {
if (a[Max + 1].second > a[Min].second) {
res--;
}
}
else {
if (a[Max + 1].second < a[Min].second) {
res++;
}
}
if (Max - Min == 1) {
if (a[Max].second < a[Min].second) {
if (a[Min].second > a[Max].second) {
res--;
}
}
else {
if (a[Min].second < a[Max].second) {
res++;
}
}
}
else {
if (a[Max].second < a[Max - 1].second) {
if (a[Min].second > a[Max - 1].second) {
res--;
}
}
else {
if (a[Min].second < a[Max - 1].second) {
res++;
}
}
if (a[Min + 1].second < a[Min].second) {
if (a[Min + 1].second > a[Max].second) {
res--;
}
}
else {
if (a[Min + 1].second < a[Max].second) {
res++;
}
}
}
swap(a[Min].second, a[Max].second);
swap(it1->second, it2->second);
cout << res << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
# a[k] = (giá trị, vị trí); a[0] và a[n + 1] là 2 lính canh
a = [(int(data[i + 1]), i) for i in range(1, n + 1)]
a.sort()
a = [(0, 0)] + a + [(n + 1, n + 1)]
sec = [p[1] for p in a] # sec[k] = a[k].second
mp = {}
for i in range(1, n + 1):
mp[sec[i]] = i
res = 1
for i in range(1, n + 1):
if sec[i] < sec[i - 1]:
res += 1
out = []
p = n + 2
for _ in range(m):
x, y = int(data[p]), int(data[p + 1])
p += 2
i, j = mp[x], mp[y]
Min, Max = min(i, j), max(i, j)
if sec[Min] < sec[Min - 1]:
if sec[Max] > sec[Min - 1]:
res -= 1
else:
if sec[Max] < sec[Min - 1]:
res += 1
if sec[Max + 1] < sec[Max]:
if sec[Max + 1] > sec[Min]:
res -= 1
else:
if sec[Max + 1] < sec[Min]:
res += 1
if Max - Min == 1:
if sec[Max] < sec[Min]:
if sec[Min] > sec[Max]:
res -= 1
else:
if sec[Min] < sec[Max]:
res += 1
else:
if sec[Max] < sec[Max - 1]:
if sec[Min] > sec[Max - 1]:
res -= 1
else:
if sec[Min] < sec[Max - 1]:
res += 1
if sec[Min + 1] < sec[Min]:
if sec[Min + 1] > sec[Max]:
res -= 1
else:
if sec[Min + 1] < sec[Max]:
res += 1
sec[Min], sec[Max] = sec[Max], sec[Min]
mp[x], mp[y] = mp[y], mp[x]
out.append(res)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Bản Python mình tách riêng danh sách sec (chính là các a[k].second) cho gọn, và dùng dict thay cho map; logic từng câu if giữ y như bản C++.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$ của mảng
a+ $O(n)$ củamap⇒ $O(2n)$, bỏ hằng số ⇒ $O(n)$. - Thời gian: đọc dữ liệu $O(n)$ + sắp xếp $O(n \log n)$ + thêm $n$ phần tử vào
map, mỗi lần $O(\log n)$ ⇒ $O(n \log n)$ (thực ramapbản chất là cây đỏ đen, còn chi phí cân bằng cây nhưng ở đây ta bỏ qua) + tínhresban đầu $O(n)$ + mỗi thao tác tìm 2 phần tử trongmapmất $O(2 \log n)$, còn lại đều $O(1)$ ⇒ $O(m \cdot 2 \log n)$. Bỏ hằng số và lấy thành phần lớn nhất: $O(\max(m, n) \cdot \log n)$.
Trường hợp lớn nhất $m = n = 2 \cdot 10^5$ thì cỡ $2 \cdot 10^5 \cdot 18 = 3.6 \cdot 10^6$, ít hơn ngưỡng $10^8$ rất nhiều nên yên tâm không bị TLE nhé các bạn.
map bằng một mảng thường idx[vị trí] = giá trị (chính là mảng ban đầu!) để tìm trong $O(1)$; độ phức tạp còn $O(n \log n + m)$, và nếu dùng luôn pos[giá trị] thay cho bước sắp xếp thì còn $O(n + m)$.-fsanitize=address,undefined -D_GLIBCXX_DEBUG) không báo lỗi. Với $n = m = 2 \cdot 10^5$: cách 2 bản C++ chạy khoảng 0.45 giây, bản Python khoảng 1.5 giây; cách 1 thì với dãy giảm dần $n = 2 \cdot 10^5$ chỉ 20 thao tác đã chạy quá 60 giây.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét