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ụ

Dữ liệu:
3
3
1
2

Kết quả
2

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! 😀

3. Code tham khảo NKINV spoj

#include <bits/stdc++.h>
#define maxn 60001
using namespace std;
    int n;
    int a[maxn], it[5*maxn];
void update(int r, int k, int l, int u, int v, int val)
{
    if(v<k||l<u) return;
    if(u<=k&&l<=v){it[r]+=val; return;}
    int g=(k+l)/2;
    update(2*r,k,g,u,v,val);
    update(2*r+1,g+1,l,u,v,val);
    it[r]=it[2*r]+it[2*r+1];
}
int get(int r, int k, int l, int u, int v)
{
    if(v<k||l<u) return 0;
    if(u<=k&&l<=v) return it[r];
    int g=(k+l)/2;
    int t1=get(2*r,k,g,u,v);
    int t2=get(2*r+1,g+1,l,u,v);
    return t1+t2;
}
int main()
{
    cin>>n;
    int m=0;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        m=max(m, a[i]);
    }
    int ds=0;
    for(int i=n; i>=1; i--)
    {
        int t=get(1,1,m,1,a[i]-1);
        ds=ds+t;
        update(1,1,m,a[i],a[i],1);
    }
    cout<<ds;
}