Thẻ

Dạng: Binary Indexed Tree
Link: http://laptrinh.ntu.edu.vn/Problem/Details/1146
Thuật toán tra cứu: https://namlunoy.wordpress.com/2015/05/17/1-ky-thuat-binary-index-tree/

Đề bài

Cho dãy n số nguyên a1, a2,…, an. Một cặp số (ai, aj) được gọi là nghịch thế nếu i aj. Hãy đếm xem trong dãy trên có bao nhiêu cặp số nghịch thế.
Dữ liệu nhập:
– Dòng đầu tiên là số nguyên n (2 ≤ n ≤ 105)
– Dòng tiếp theo là n số nguyên a1, a2,…, an, mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ 10^9)
Dữ liệu xuất:
– Là số cặp nghịch thế đếm được.
Ví dụ
input
3
3 1 2
output
2
input
5
7 4 4 3 1
output
9

Solution

Với cận nhỏ có thể có thể sử dụng BIT với các node thể hiện giá trị của đó (giống như bài cái túi)!
Nhưng với cận lớn thì phải kết hợp thê kỹ thuật sort, và các node đánh giá trị theo chỉ số của nó!

Nỗi phần tử ở đây ta quy định nó có 2 dữ liệu, đó là value và index!
Sau đó ta sắp xếp giảm dần (hoặc tăng dần thì các bước sau làm ngược lại).
Như vậy, phần tử sau sẽ có value nhỏ hơn phần tử trước!
Nhưng nếu có index lơn hơn phần tử trước tức là nó ở đăng sau (nhưng lại có value nhỏ hơn) nên đó là 1 cặp nghịch thế!

Thuật toán như sau:
*) Ta đi từ đầu đến cuối dãy đã được sắp xếp, ở đây làm giảm dần
*) t[i] là gì?
Gọi t[i] : là số lượng chỉ số nhỏ hơn nó!
Tại sao: tại vì khi duyệt đến vị trí thứ i (nhỏ hơn các vị trí trước), số lượng cặp nghịch thế mà nó có thể tạo ra, bằng số lượng các phần tử lớn hơn (đã được đáp ứng bằng việc sắp xếp giảm dần) và đứng trước nó (chính là cái ta đang định nghĩa ở đây!)

*) t[i] + 1 khi nào?
Khi gặp phần tử có index là k, do t[k] là số phần tử có index nhỏ hơn k, mà index nhỏ hơn k thì nhỏ hơn k+1!
=> Cập nhật lên trên từ vị trí k+1

Ta xét: dãy 7 4 3 2 1
kết quả lần lượt là 1+2+3+4 = 10.

Nhưng với dãy 7 4 4 3 2
Thì nó sẽ có vấn đề!
Do nó vẫn nhận cặp (4,4) là 1 cặp nghịch thế!
Như vậy 2 số giống nhau nó cần có index giống nhau thì làm mới đúng được!
=> Trong quá trình sắp xếp và đặt chỉ số ta nên lưu ý vấn đề này!

Đã tìm ra lỗi sai!
Quan trọng là lúc sắp xếp ta sắp xếp đúng kiểu thì thực hiện phép trên mới đúng được!
Sắp xếp sai là sẽ sai!

Advertisements