NKINV spoj – Dãy nghịch thế (cây IT)

Nguồn đề bài: http://vn.spoj.com/problems/NKINV/

1. Đề bài NKINV spoj

Cho một dãy số a₁.. a_N. Một nghịch thế là một cặp số u, v sao cho u < v và a_u > a_v. 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ố a_i ( 1 ≤ i ≤ N ).

Kết quả

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 ≤ a_i ≤ 60000

Ví dụ

2. Hướng dẫn NKINV spoj

Bài này mình sẽ bày cách cho các bạn dùng cây IT để làm:

Vì 1<=ai<=60000 nên ta dùng một mảng it[60001] để đánh dấu sự xuất hiện của các giá trị.  it[i]=k tức là trong đoạn ta xét hiện thời, số i đã xuất hiện k lần.

Khởi đầu số nghịch thế bằng 0: ds=0.

Ta xét từ cuối mảng tới đầu mảng, mỗi lần gặp giá trị a[i], ta tính tổng các số trong mảng it từ 1 tới a[i]-1. Tức là tính xem có bao nhiêu số nhỏ hơn số a[i] đã xuất hiện. (Phần này dùng it tổng.) Sau đó cập nhật a[i] vào cây, tăng it[a[i]] lên một đơn vị.

Nếu các bạn chưa hiểu có thể cmt để hỏi thêm. Cảm ơn!