let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

NKINV - Dãy nghịch thế

solution.md

Gọi \(C[x]\) là số lượng giá trị \(x\) đã xuất hiện. Duyệt các phần tử từ đầu dãy đến cuối dãy, mối lần duyệt ta tính tổng từ \(C[x+1]\) đến cuối mảng \(C\) rồi thêm vào kết quả, sau đó tăng \(C[x]\) (\(x\) là phần tử đang xét).

Để AC cần sử dụng cấu trúc Fenwick Tree để giảm độ phức tạp của phương pháp trên xuống còn \(O(N\log C)\).

Lưu ý là ta cần tính tổng từ một vị trí đến cuỗi dãy, ngược lại với phiên bản trong bài viết trên.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

#define LL long long

struct Fenwick {
    int n;
    vector<LL> f;
    Fenwick(int n): n(n), f(n+1, 0) {}
    void set(int i) {
        for (; i>=1; i -= i&(-i)) f[i]++;
    }
    LL get(int i) {
        LL result = 0;
        for (; i<=n; i += i&(-i)) result += f[i];
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    Fenwick f(60000);
    LL result = 0;
    while (n--) {
        LL x; cin >> x;
        result += f.get(x+1);
        f.set(x);
    }
    cout << result;

    return 0;
}
Comments