rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: verify/lc_data_structure/lc_static_range_inversions_query.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <bits/stdc++.h>

#include "misc/mo.hpp"
#include "data_structure/fenwick_tree.hpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) std::cin >> L[i] >> R[i];

    auto B = A;
    std::sort(B.begin(), B.end());
    B.erase(std::unique(B.begin(), B.end()), B.end());
    for (auto &&e : A) e = std::lower_bound(B.begin(), B.end(), e) - B.begin();

    const int M = (int)B.size();
    FenwickTree<long long> fen(M);
    std::vector<long long> ans(Q);
    long long cur = 0;
    auto add_left = [&](int i) {
        cur += fen.sum(A[i]);
        fen.add(A[i], 1);
    };
    auto add_right = [&](int i) {
        cur += fen.sum(A[i] + 1, M);
        fen.add(A[i], 1);
    };
    auto del_left = [&](int i) {
        cur -= fen.sum(A[i]);
        fen.add(A[i], -1);
    };
    auto del_right = [&](int i) {
        cur -= fen.sum(A[i] + 1, M);
        fen.add(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = cur; };
    mo(N, L, R, add_left, add_right, del_left, del_right, out);
    for (int i = 0; i < Q; i++) std::cout << ans[i] << '\n';
    return 0;
}
#line 1 "verify/lc_data_structure/lc_static_range_inversions_query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <bits/stdc++.h>

#line 2 "misc/mo.hpp"

// Mo's Algorithm
// https://snuke.hatenablog.com/entry/2016/07/01/000000
// complexity: O(N^2/B + QB)
// -> O(N sqrt(Q)) (B := N / sqrt(Q))
template <class AddLeft, class AddRight, class DelLeft, class DelRight, class Out>  //
void mo(const int &n, const std::vector<int> &l, const std::vector<int> &r,         //
        const AddLeft &add_left, const AddRight &add_right,                         //
        const DelLeft &del_left, const DelRight &del_right, const Out &out) {
    const int q = (int)l.size();
    if (q == 0) return;
    // normal
    // const int bucket_size = std::max(1.0, n / std::max(1.0, sqrt(q)));
    // speed up by https://nyaannyaan.github.io/library/misc/mo.hpp
    const int bucket_size = std::max(1.0, n / std::max(1.0, sqrt(2.0 * q / 3.0)));
    std::vector<int> ind(q), lbs(q);
    // reduce the number of divisions by memoization
    for (int i = 0; i < q; i++) lbs[i] = l[i] / bucket_size;
    std::iota(ind.begin(), ind.end(), 0);
    std::sort(ind.begin(), ind.end(), [&](int i, int j) {
        if (lbs[i] != lbs[j]) return l[i] < l[j];
        return (lbs[i] & 1) ? r[i] > r[j] : r[i] < r[j];
    });
    // initialize with [ l[ind[0]], l[ind[0]] ) instead of [0, 0)
    int now_l = l[ind[0]], now_r = now_l;
    for (auto &&i : ind) {
        while (now_l > l[i]) add_left(--now_l);
        while (now_r < r[i]) add_right(now_r++);
        while (now_l < l[i]) del_left(now_l++);
        while (now_r > r[i]) del_right(--now_r);
        out(i);
    }
}
template <class Add, class Del, class Out>                                  //
void mo(const int n, const std::vector<int> &l, const std::vector<int> &r,  //
        const Add &add, const Del &del, const Out &out) {
    mo(n, l, r, add, add, del, del, out);
}
#line 2 "data_structure/fenwick_tree.hpp"

template <class T> struct FenwickTree {
    int n;
    std::vector<T> seg;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), seg(n + 1, 0) {}
    FenwickTree(std::vector<T>& arr) {
        n = int(arr.size());
        seg.resize(n + 1);
        for (int i = 0; i < n; i++) add(i, arr[i]);
    }
    // A[i] += x
    void add(int i, const T& x) {
        assert(0 <= i and i < n);
        i++;  // 1-indexed
        while (i <= n) {
            seg[i] += x;
            i += i & -i;
        }
    }
    // A[0] + ... + A[i - 1]
    T sum(int i) const {
        assert(0 <= i and i <= n);
        T s = T(0);
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    }
    // A[a] + ... + A[b - 1]
    T sum(int a, int b) const {
        assert(0 <= a and a <= b and b <= n);
        return sum(b) - sum(a);
    }
    // return A[i]
    T get(int i) const { return sum(i, i + 1); }
    // A[i] = x
    void set(int i, const T x) { add(i, x - get(i)); }
    // output
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& fen) {
        for (int i = 0; i < fen.n; i++) os << fen.get(i) << " \n"[i == fen.n - 1];
        return os;
    }
};
#line 7 "verify/lc_data_structure/lc_static_range_inversions_query.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) std::cin >> L[i] >> R[i];

    auto B = A;
    std::sort(B.begin(), B.end());
    B.erase(std::unique(B.begin(), B.end()), B.end());
    for (auto &&e : A) e = std::lower_bound(B.begin(), B.end(), e) - B.begin();

    const int M = (int)B.size();
    FenwickTree<long long> fen(M);
    std::vector<long long> ans(Q);
    long long cur = 0;
    auto add_left = [&](int i) {
        cur += fen.sum(A[i]);
        fen.add(A[i], 1);
    };
    auto add_right = [&](int i) {
        cur += fen.sum(A[i] + 1, M);
        fen.add(A[i], 1);
    };
    auto del_left = [&](int i) {
        cur -= fen.sum(A[i]);
        fen.add(A[i], -1);
    };
    auto del_right = [&](int i) {
        cur -= fen.sum(A[i] + 1, M);
        fen.add(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = cur; };
    mo(N, L, R, add_left, add_right, del_left, del_right, out);
    for (int i = 0; i < Q; i++) std::cout << ans[i] << '\n';
    return 0;
}
Back to top page