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ố 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 ).

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 ≤ ai ≤ 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;
}

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

  1. – Có thể giải thích tại sao mình copy code của bạn nộp ở NTUCoder lại WA test 14 không?.. trong lúc mình nộp ở SPOJ thì 100đ.

    • ở đây. r là gốc, quản lí các nút trong đoạn từ k đến l. bạn có thể tìm hiểu thêm trong các bài viết về cây IT. cảm ơn bạn.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *