Hướng giải của [Mo's] Nghịch Thế

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Đây là bài toán đếm số cặp nghịch thế trong đoạn, sử dụng Mo's Algorithm kết hợp Fenwick Tree (BIT).

Ý tưởng:

  • Duy trì một BIT trên các giá trị đã nén.
  • Khi thêm một phần tử bên phải (++curR):
    • Đếm số phần tử hiện có lớn hơn giá trị vừa thêm.
    • curAns += totalElements - BIT.query(compressedValue).
  • Khi thêm một phần tử bên trái (--curL):
    • Đếm số phần tử hiện có nhỏ hơn giá trị vừa thêm.
    • curAns += BIT.query(compressedValue - 1).
  • Khi xóa một phần tử bên trái (curL++):
    • Trừ đi số phần tử nhỏ hơn nó (tính trước khi xóa).
    • curAns -= BIT.query(compressedValue - 1).
  • Khi xóa một phần tử bên phải (curR--):
    • Trừ đi số phần tử lớn hơn nó.
    • curAns -= (totalElements - BIT.query(compressedValue)).

Độ phức tạp: \(O((N+Q)\sqrt{N} \log N)\).

Mã nguồn C++

// Giải thuật mo cho bài toán mo-inversion\n#include <bits/stdc++.h>
using namespace std;

int blockSize;
struct Query {
    int l, r, idx;
    bool operator<(const Query& o) const {
        int bl = l / blockSize, br = o.l / blockSize;
        if (bl != br) return bl < br;
        return (bl & 1) ? (r > o.r) : (r < o.r);
    }
};

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n): n(n), bit(n + 2, 0) {}
    void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    int range(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> comp = a;
    sort(comp.begin(), comp.end());
    // Sap xep mang
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int m = comp.size();
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;

    blockSize = max(1, (int)sqrt(n));
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--; queries[i].r--;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end());
    // Sap xep mang

    vector<long long> ans(q);
    BIT bit(m);
    long long curAns = 0;
    int curL = 0, curR = -1;
    int total = 0;

    auto add_right = [&](int pos) {
        int v = a[pos];
        curAns += total - bit.sum(v);
        bit.add(v, 1);
        total++;
    };
    auto add_left = [&](int pos) {
        int v = a[pos];
        curAns += bit.sum(v - 1);
        bit.add(v, 1);
        total++;
    };
    auto remove_left = [&](int pos) {
        int v = a[pos];
        bit.add(v, -1);
        total--;
        curAns -= bit.sum(v - 1);
    };
    auto remove_right = [&](int pos) {
        int v = a[pos];
        bit.add(v, -1);
        total--;
        curAns -= total - bit.sum(v);
    };

    for (auto& qr : queries) {
        while (curL > qr.l) add_left(--curL);
        while (curR < qr.r) add_right(++curR);
        while (curL < qr.l) remove_left(curL++);
        while (curR > qr.r) remove_right(curR--);
        ans[qr.idx] = curAns;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.