Bài viết này bàn về một hướng suy nghĩ giải quyết bài NKINV.
Chú ý: Để nắm được toàn bộ tư tưởng bài viết, mình đề nghị các bạn (nếu chưa từng) đọc qua nội dung kiến thức về một kiểu cấu trúc dữ liệu đặc biệt nổi tiếng, đó là Binary Indexed Tree (BIT). Thuật toán chính giới thiệu trong bài này sử dụng cấu trúc dữ liệu đó. Lưu ý rằng mình sẽ không nói đến hoạt động của BIT như thế nào mà vấn đề chính đề cập tới chính là làm thế nào xuất hiện ý tưởng sử dụng BIT.
Cho một dãy số a1.. aN. Một nghịch thế là một cặp số u, v sao cho u < v và au > av. Nhiệm vụ của bạn là đếm số nghịch thế.
Dữ liệu- Dòng đầu ghi số nguyên dương N.
- N dòng sau mỗi dòng ghi một số ai ( 1 ≤ i ≤ N ).
Ghi trên một dòng số M duy nhất là số nghịch thế.
Giới hạn- 1 ≤ N ≤ 60000
- 1 ≤ ai ≤ 60000
Dữ liệu: 3 3 1 2 Kết quả 2
Thuật toán đơn giản nhất cho bài này đó là Brute-Force: kiểm tra tất cả các cặp (u, v) (u < v) nếu au > av thì tăng biến kết quả lên 1.
for i := 1 to n - 1 do
for j := i + 1 to n do
if a[i] > a[j] then result := result + 1;
Thuật toán này tuy rất đơn giản nhưng độ phức tạp quá lớn (cỡ O(n2)), không thể chạy với N ≤ 60000 trong 1s được. Do đó ta sẽ đi tìm thuật toán khác với độ phức tạp nhỏ hơn để giải bài này.
Đã tới giờ tưởng tượng ! Hãy thử tưởng tượng, bằng cách nào đó bạn có được một dãy số b[x] với b[x] chính là số số lớn hơn x (x = a[i] nào đó) trong dãy a, xét từ phần tử thứ nhất đến phần tử x đang xét. Bạn hiểu ý chỗ này chứ ? Tức là giả sử bạn đang xét đến phần tử mang giá trị x nào đó trong dãy a, bạn sẽ có một số b[x] là số số lớn hơn x trong dãy a[1..j] (j là vị trí của phần tử x trong a). Để ý rằng dãy b sẽ thay đổi theo thời gian và hơn nữa, các phần tử của b cũng như số phần tử của b sẽ không vượt quá 60000 (vì 1 ≤ ai ≤ 60000)
Vậy khi có dãy b, ta sẽ làm gì ? Khi có dãy b, ta sẽ chỉ đơn giản là cộng b[x] vào result, bởi vì phần tử hiện tại là x và ta biết có b[x] số nằm trước x trong dãy a và lớn hơn x, do đó kết quả thực sự sẽ tăng thêm b[x] cặp nghịch thế nữa. Do đó vấn đề của chúng ta hiện tại chính là tính được b[x] mà thôi. Ta sẽ lần lượt xét các phương án từ cơ bản đến phức tạp hơn dưới đây.
Phương án thứ nhất mà ai cũng nghĩ ra, đó chính là duyệt toàn bộ các phần tử nằm trước x trong a (giả sử vị trí của x là j, thì toàn bộ các phần tử 1..j - 1 sẽ được xét đến) và với mỗi cặp nghịch thế tìm được, ta sẽ tăng 1 vào b[x]. Cách này chẳng khá khẩm gì hơn thuật toán Brute-Force, thậm chí còn tệ hơn vì sử dụng đến hai mảng a, b. Do đó, ta loại cách này.
Phương án thứ hai, ta thử xây dựng một bảng tần số g, trong đó g[x] là số lần xuất hiện của phần tử x trong dãy a[1..j - 1]. Khi đó, b[x] := Σ g[x + 1..60000] (ở đây 60000 chính là giá trị tối đa của a[i], không phải giá trị lớn nhất của n-số phần tử). Việc xây dựng bảng tần số g chỉ mất O(1) cho mỗi số x, tức là O(n) xét toàn tập dữ liệu. Vì vậy, vấn đề cuối cùng của chúng ta là tính các tổng b[1..60000] mà thôi. Yêu cầu này gợi ý chúng ta đến việc sử dụng cấu trúc dữ liệu BIT (tức là IT và RMQ đều được) để xây dựng và lưu trữ dãy b trong thời gian O(mlogn).
Mình xin được nêu một số gợi ý để sử dụng BIT (ý kiến cá nhân): Nếu bài toán xuất hiện yêu cầu xử lí các khoảng số và tính các tổng liên tiếp của dãy số (bảng số, khối số, ...) thì có thể nghĩ tới dùng BIT để xử lí (điều này chỉ là một suy nghĩ của người mới biết tới BIT được 2 ngày, chưa phải chân lí).
Vậy quay lại với bài toán. Ta thấy trong tài liệu BIT (mình đã đặt link ở đầu bài), mỗi phần tử tree[i] sẽ lưu tổng của một đoạn nằm phía trước (bao gồm cả phần tử a[i]) của phần tử a[i] mà trong bài này lại yêu cầu tính tổng phía sau. Vậy thì hoặc là ta đảo cả mảng tree lại, hoặc là ta "lật" phần mà tree[i] quản lí lại, tức là tree[i] sẽ không quản lí nửa phía trước mà là nửa phía sau của đoạn đó (bạn nên xem hình sẽ rõ hơn).
Trong tài liệu:
Còn đối với chúng ta, ta sẽ quan tâm tới cây BIT có dạng như sau:Vậy khi có dãy b, ta sẽ làm gì ? Khi có dãy b, ta sẽ chỉ đơn giản là cộng b[x] vào result, bởi vì phần tử hiện tại là x và ta biết có b[x] số nằm trước x trong dãy a và lớn hơn x, do đó kết quả thực sự sẽ tăng thêm b[x] cặp nghịch thế nữa. Do đó vấn đề của chúng ta hiện tại chính là tính được b[x] mà thôi. Ta sẽ lần lượt xét các phương án từ cơ bản đến phức tạp hơn dưới đây.
Phương án thứ nhất mà ai cũng nghĩ ra, đó chính là duyệt toàn bộ các phần tử nằm trước x trong a (giả sử vị trí của x là j, thì toàn bộ các phần tử 1..j - 1 sẽ được xét đến) và với mỗi cặp nghịch thế tìm được, ta sẽ tăng 1 vào b[x]. Cách này chẳng khá khẩm gì hơn thuật toán Brute-Force, thậm chí còn tệ hơn vì sử dụng đến hai mảng a, b. Do đó, ta loại cách này.
Phương án thứ hai, ta thử xây dựng một bảng tần số g, trong đó g[x] là số lần xuất hiện của phần tử x trong dãy a[1..j - 1]. Khi đó, b[x] := Σ g[x + 1..60000] (ở đây 60000 chính là giá trị tối đa của a[i], không phải giá trị lớn nhất của n-số phần tử). Việc xây dựng bảng tần số g chỉ mất O(1) cho mỗi số x, tức là O(n) xét toàn tập dữ liệu. Vì vậy, vấn đề cuối cùng của chúng ta là tính các tổng b[1..60000] mà thôi. Yêu cầu này gợi ý chúng ta đến việc sử dụng cấu trúc dữ liệu BIT (tức là IT và RMQ đều được) để xây dựng và lưu trữ dãy b trong thời gian O(mlogn).
Mình xin được nêu một số gợi ý để sử dụng BIT (ý kiến cá nhân): Nếu bài toán xuất hiện yêu cầu xử lí các khoảng số và tính các tổng liên tiếp của dãy số (bảng số, khối số, ...) thì có thể nghĩ tới dùng BIT để xử lí (điều này chỉ là một suy nghĩ của người mới biết tới BIT được 2 ngày, chưa phải chân lí).
Vậy quay lại với bài toán. Ta thấy trong tài liệu BIT (mình đã đặt link ở đầu bài), mỗi phần tử tree[i] sẽ lưu tổng của một đoạn nằm phía trước (bao gồm cả phần tử a[i]) của phần tử a[i] mà trong bài này lại yêu cầu tính tổng phía sau. Vậy thì hoặc là ta đảo cả mảng tree lại, hoặc là ta "lật" phần mà tree[i] quản lí lại, tức là tree[i] sẽ không quản lí nửa phía trước mà là nửa phía sau của đoạn đó (bạn nên xem hình sẽ rõ hơn).
Trong tài liệu:
Chú ý rằng các số liệu trong hình là không liên quan tới bài toán, các bạn chỉ cần để ý tới các thanh dọc là được rồi. Một lưu ý nhỏ là phần tử lớn nhất (maxnum, trong hình là 16) thì không có giá trị nào lớn hơn nữa, do đó tree[16] là không cần thiết phải lưu, ta ngầm định nó bằng 0.
Như vậy, sử dụng cấu trúc BIT, ta sẽ giải bài tập này trong thời gian ngắn hơn thuật toán Brute-Force. Có thể rút xuống còn sử dụng một mảng tree[1..n] mà thôi. Code bên dưới dùng mảng ff[1..n] thay vì mảng tree[1..n].
Code:
Lưu ý: dữ liệu vào định dạng như trong đề bài, lưu trong file VNOI_NKINV.INP để chạy.
