Dãy nghịch thế (NKINV)

Nguồn: VNOJ (IOICamp Marathon 2005-2006) Độ khó: Khá Đếm Ordered Set Cấu trúc dữ liệu

Đề bài

Dãy nghịch thế (NKINV)

Giới hạn thời gian: 1 giây. Giới hạn bộ nhớ: 512 MB.

Cho một dãy số $a_1, \ldots, a_N$. Một nghịch thế là một cặp số $u, v$ sao cho $u \lt v$ và $a_u \gt a_v$. Nhiệm vụ của bạn là đếm số nghịch thế.

Input:

• Dòng đầu ghi số nguyên dương $N$.
• $N$ dòng sau mỗi dòng ghi một số $a_i$ $(1 \le i \le N)$.
• $1 \le N \le 60000$
• $1 \le a_i \le 60000$

Output:

• Ghi trên một dòng số $M$ duy nhất là số nghịch thế.

Sample Input

3
3
1
2

Sample Output

2

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải chi tiết để các bạn cùng tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Giải thích lại đề cho bạn nào chưa hiểu: ta cần đếm xem có bao nhiêu cặp vị trí $(u, v)$ mà số đứng trước ($a_u$) lại lớn hơn số đứng sau ($a_v$). Nói cách khác: khi đọc từng số từ input vào, với mỗi số ta đếm xem có bao nhiêu số đứng trước nó mà lớn hơn nó, rồi cộng hết các số lượng đó lại là ra đáp án.

Với ví dụ, 3 số lần lượt trong input là $3, 1, 2$:

• Đầu tiên số $3$ đưa vào, trước đó không có số nào cả, nên số lượng số đứng trước lớn hơn nó là $0$.
• Xét số $1$: trong các số trước đó $\{3\}$ có bao nhiêu số lớn hơn $1$? Chỉ có số $3$ ⇒ $1$ số. Tổng kết quả là $1$.
• Xét số $2$: danh sách trước đó đang có $\{3, 1\}$, chỉ có $1$ số lớn hơn $2$ (là số $3$) ⇒ cộng thêm $1$, tổng là $2$.
• Hết số trong input rồi, kết quả sau cùng là $2$, in ra $2$. Hai nghịch thế chính là cặp $(3, 1)$ và $(3, 2)$.

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn · O(N²) · TLECách 2Ordered Set (pbds) · O(N log N)

Cách 1Vét cạn: xét lại hết các số đứng trước – O(N²)

Đây là cách dễ dàng nhất theo đúng ý tưởng ở trên: cứ đọc một số từ input vào, ta xét trong mảng hiện tại có bao nhiêu thằng lớn hơn thằng vừa đọc vào. Có số lượng cụ thể rồi thì cộng vào biến kết quả, đưa phần tử hiện tại vào mảng, rồi lại đọc phần tử mới và lặp lại quy trình đó.

Nếu làm theo cách cơ bản nhất là cứ tìm kiếm tuần tự trong mảng, thì tổng số lượng phần tử phải xét sẽ là:

Tổng số lần xét

$0 + 1 + 2 + 3 + \ldots + (N - 1) = \dfrac{N(N - 1)}{2}$

• $0$ là vì sao? Vì khi số thứ 1 đọc từ input vào thì trong mảng đang có $0$ phần tử.
• $1$ là vì sao? Vì khi số thứ 2 đọc vào thì mảng đang có $1$ phần tử, nên phải xét qua hết để biết có bao nhiêu thằng lớn hơn số vừa đọc vào.
• Cứ thế đến khi số cuối cùng (số thứ $N$) đọc vào thì mảng đang có $N - 1$ phần tử, tìm kiếm tuần tự thì phải xét hết qua $N - 1$ phần tử này.

Nhân vào ta được $\dfrac{N^2 - N}{2} = (N^2 - N) \cdot 0.5$. Theo quy tắc nhân Big-O, nhân với hằng số thì bỏ qua, còn lại $N^2 - N = N^2 + (-N)$. Theo quy tắc cộng Big-O thì lấy thành phần lớn nhất, giữa $N^2$ và $-N$ thì chắc chắn $N^2$ lớn hơn ⇒ độ phức tạp là $O(N^2)$.

Không đáp ứng được time limit

Đề cho $N$ tối đa là $60000 = 6 \cdot 10^4$, nên $N^2 = 36 \cdot 10^8$. Code C/C++ với time limit 1 giây thì ngưỡng an toàn chỉ cỡ $10^8$ phép tính, ở đây gấp tận 36 lần (kể cả chia đôi thì vẫn $1.8 \cdot 10^9$) ⇒ làm theo cách này chắc chắn không ổn.

Tuy là thế nhưng mình vẫn code cách vét cạn để các bạn tham khảo, vừa để hiểu đề, vừa để làm code đối chiếu khi kiểm tra cách tối ưu:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    long long res = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        for(int j = 0; j < i; ++j){
            if(a[i] < a[j]){
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = []
res = 0
for i in range(n):
    x = int(data[i + 1])
    for j in range(i):
        if x < a[j]:
            res += 1
    a.append(x)
print(res)

C++▶ Chạy tay từng dòng codeVét cạn: mỗi a[i] đọc vào, đếm các a[j] (j < i) lớn hơn nó.

Dữ liệu vào (stdin) – sửa thoải mái3 3 1 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 int a[n];

11 long long res = 0;

12 for(int i = 0; i < n; ++i){

13 cin >> a[i];

14 for(int j = 0; j < i; ++j){

15 if(a[i] < a[j]){

16 res++;

17 }

18 }

19 }

20 cout << res;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng a.
• Thời gian: $O(N^2)$ như đã phân tích ở trên.

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 2Ordered Set lưu cả số trùng – O(N log N)

Giờ ta cần tối ưu lại cho tốt hơn. Ta thấy nếu cứ phải tìm kiếm tuần tự thì sẽ không tốt bằng tìm kiếm nhị phân đúng không? Nhưng vấn đề là muốn tìm kiếm nhị phân thì danh sách phải có thứ tự, mà dữ liệu trong input đề không hề nói là có thứ tự, nó là ngẫu nhiên.

Vậy nếu dùng mảng, chẳng lẽ cứ mỗi lần đọc 1 thằng vào, tìm kiếm nhị phân xong rồi đưa phần tử đó vào mảng và gọi lại hàm sort? Mỗi lần gọi sort tốn $O(N \log N)$, gọi $N$ lần thì thành $O(N^2 \log N)$, còn cao hơn cả việc đi tìm kiếm tuần tự nữa 😅.

Lúc này không có cách nào khác ngoài việc dùng cấu trúc dữ liệu dạng cây để lưu trữ phần tử. Cây theo quy luật nhỏ qua trái, lớn qua phải và phân ra từng tầng, nên mọi thao tác thêm, xóa, tìm kiếm chỉ tốn $O(\log N)$. Thêm $N$ phần tử ⇒ $O(N \log N)$. Thay vì cứ dùng mảng rồi liên tục sort thì dùng cây sẽ tốt hơn nhiều. Và ta cần một cấu trúc cây có hỗ trợ đếm theo thứ tự trên đó.

Ordered Set và hàm order_of_key

Trong C++ (trình biên dịch GNU) có cấu trúc Ordered Set thuộc thư viện __gnu_pbds rất thuận tiện: nó có sẵn hàm order_of_key(x) trả ra xem hiện tại trong cây đang có bao nhiêu phần tử có giá trị < x, chỉ tốn $O(\log N)$. Các bạn có thể tận dụng nó cho những bài toán cần đếm số lượng phần tử nhỏ hơn, lớn hơn một giá trị cụ thể nào đó.

Đếm các loại từ order_of_key

• Số phần tử $\lt x$: s.order_of_key(x).
• Số phần tử $\ge x$: s.size() - s.order_of_key(x) (tổng số phần tử trừ đi số phần tử $\lt x$).
• Số phần tử $\le x$: s.order_of_key(x + 1), tức là đếm các phần tử $\lt x + 1$, tương đương $\le x$ (vì toàn số nguyên).
• Số phần tử $\gt x$: s.size() - s.order_of_key(x + 1) (tổng trừ đi số phần tử $\le x$). Đây chính là cái bài này cần!

Có 1 vấn đề là cấu trúc nguyên thủy của Ordered Set chỉ lưu các phần tử phân biệt, không trùng nhau (bản chất của Set là vậy mà). Trong khi bài dãy nghịch thế không hề nói các phần tử đều phân biệt, nên không dùng được Ordered Set chính quy, mà ta cần "độ nó lại" 1 chút để lưu được cả những phần tử trùng nhau.

Mẹo lưu số trùng: dùng pair (giá trị, vị trí)

Thay vì lưu x, ta lưu cặp {x, i} với i là vị trí của nó trong dãy. Hai số bằng nhau thì vị trí khác nhau, nên các cặp luôn phân biệt. Các cặp được so sánh theo giá trị trước, cùng giá trị thì so theo vị trí, nên thứ tự trong cây vẫn là thứ tự tăng dần của giá trị.

Vậy với cây chứa các cặp, muốn đếm số phần tử có giá trị $\le x$ thì gọi order_of_key({x + 1, -1}): mọi cặp {v, j} có v ≤ x đều nhỏ hơn {x + 1, -1}, còn cặp có v ≥ x + 1 thì luôn lớn hơn (vì vị trí j ≥ 0 > -1). Lúc xử lý số thứ i (đếm từ 0) thì trong cây đang có đúng i phần tử, nên:

Công thức

Số phần tử đứng trước lớn hơn x = i - mySet.order_of_key({x + 1, -1}). Cộng vào res rồi insert({x, i}) vào cây.

Minh hoạ

Em nhập dãy số rồi bấm Tiếp: ô cam là số đang đọc vào, hàng dưới là cây (Ordered Set) luôn được giữ tăng dần; ô đỏ là các số lớn hơn số vừa đọc (mỗi ô đỏ là một nghịch thế), ô xanh là các số $\le$ nó.

Dãy a

Ví dụ nhanh:

Source code giải quyết theo tư tưởng mình đã trình bày ở trên (bản C++ đã nộp thành công trên VNOJ):

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// Ordered set lưu pair<giá trị, vị trí> để chứa được cả các số trùng nhau
typedef tree<pair<int, int>, null_type, less<pair<int, int>>,
             rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n;
    ordered_set_pair mySet;
    long long res = 0;
    for(int i = 0; i < n; ++i){
        cin >> x;
        res += i - mySet.order_of_key({x + 1, -1});
        mySet.insert({x, i});
    }
    cout << res;
    return 0;
}

import sys
from bisect import bisect_right, insort

data = sys.stdin.read().split()
n = int(data[0])
lst = []  # các số đã đọc, luôn giữ tăng dần
res = 0
for i in range(n):
    x = int(data[i + 1])
    # bisect_right(lst, x) = số phần tử <= x, nên i - đó = số phần tử > x
    res += i - bisect_right(lst, x)
    insort(lst, x)
print(res)

Về bản Python

Python không có sẵn Ordered Set như __gnu_pbds, nên mình giữ một list luôn tăng dần: bisect_right(lst, x) tìm kiếm nhị phân ra số phần tử $\le x$ (đúng vai trò của order_of_key(x + 1)), còn insort chèn x vào đúng chỗ. Bước chèn về lý thuyết là $O(N)$ do phải dời phần tử, nhưng việc dời này được làm bằng một lệnh chép bộ nhớ rất nhanh, nên với $N = 60000$ vẫn chạy chưa tới 1 giây. Ở đây list có thể chứa số trùng thoải mái nên không cần mẹo pair.

C++▶ Chạy tay từng dòng codeMỗi x đọc vào: res += i − (số phần tử ≤ x trong cây), rồi chèn {x, i} vào cây.

Dữ liệu vào (stdin) – sửa thoải mái3 3 1 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2#include <ext/pb_ds/assoc_container.hpp>

3#include <ext/pb_ds/tree_policy.hpp>

4using namespace std;

5using namespace __gnu_pbds;

6

7// Ordered set lưu pair<giá trị, vị trí> để chứa được cả các số trùng nhau

8typedef tree<pair<int, int>, null_type, less<pair<int, int>>,

9 rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

10

11int main(){

12 ios::sync_with_stdio(0);

13 cin.tie(0);

14 cout.tie(0);

15 int n, x;

16 cin >> n;

17 ordered_set_pair mySet;

18 long long res = 0;

19 for(int i = 0; i < n; ++i){

20 cin >> x;

21 res += i - mySet.order_of_key({x + 1, -1});

22 mySet.insert({x, i});

23 }

24 cout << res;

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho cây chứa tối đa $N$ cặp.
• Thời gian: mỗi số đọc vào tốn một lần order_of_key và một lần insert, mỗi thao tác $O(\log N)$ ⇒ tổng $O(N \log N)$, với $N = 6 \cdot 10^4$ chỉ cỡ $10^6$ phép tính, quá thoải mái.

Không gian$O(N)$

Thời gian$O(N \log N)$

Nhớ dùng long long cho res

Dãy giảm dần $60000, 59999, \ldots, 1$ có $\dfrac{60000 \cdot 59999}{2} = 1\,799\,970\,000$ nghịch thế, sát nút giới hạn int ($\approx 2.147 \cdot 10^9$). Dùng long long cho chắc ăn, đề mà nới $N$ thêm chút xíu là int tràn ngay.

Mở rộng

Bài này nằm trong nhóm bài Segment Tree / Fenwick Tree (BIT) trên VNOJ: vì $a_i \le 60000$ nên cũng có thể đếm bằng cây chỉ số nhị phân trên miền giá trị. Nhưng với Ordered Set thì code ngắn gọn hơn nhiều, và hàm order_of_key còn dùng được cho rất nhiều bài đếm "bao nhiêu phần tử nhỏ hơn / lớn hơn" khác nữa.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có nhiều số trùng), so với code vét cạn đếm mọi cặp – khớp hết. Với $N = 60000$: cách 2 bản C++ chạy khoảng 0.04 giây, bản Python khoảng 0.3–0.5 giây; cách 1 bản C++ mất 1.2–1.6 giây (vượt 1 giây), bản Python chạy hơn 100 giây chưa xong ⇒ đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇