Library

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

View the Project on GitHub ebi-fly13/Library

:heavy_check_mark: test/data_structure/Static_Range_Inversion_Query.test.cpp

Depends on

Code

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

#include <algorithm>

#include <cstdint>

#include <iostream>

#include <numeric>

#include <vector>


#include "../../algorithm/mo_algorithm.hpp"

#include "../../data_structure/compress.hpp"

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


using u64 = std::uint64_t;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    std::vector<int> l(q), r(q);
    ebi::compress<int> cp;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        cp.add(a[i]);
    }
    cp.build();
    for (int i = 0; i < n; i++) {
        a[i] = cp.get(a[i]);
    }
    for (int i = 0; i < q; i++) {
        std::cin >> l[i] >> r[i];
    }
    ebi::fenwick_tree<u64> fw(cp.size());
    std::vector<u64> ans(q);
    u64 ret = 0;
    const auto insert_left = [&](int l) -> void {
        ret += fw.prefix_sum(a[l]);
        fw.add(a[l], 1);
    };
    const auto insert_right = [&](int r) -> void {
        ret += fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], 1);
    };
    const auto delete_left = [&](int l) -> void {
        ret -= fw.prefix_sum(a[l]);
        fw.add(a[l], -1);
    };
    const auto delete_right = [&](int r) -> void {
        ret -= fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], -1);
    };
    const auto out = [&](int i) -> void { ans[i] = ret; };
    ebi::mo_algorithm(n, l, r, insert_left, insert_right, delete_left,
                      delete_right, out);
    for (auto val : ans) {
        std::cout << val << '\n';
    }
}
#line 1 "test/data_structure/Static_Range_Inversion_Query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <algorithm>

#include <cstdint>

#include <iostream>

#include <numeric>

#include <vector>


#line 2 "algorithm/mo_algorithm.hpp"

#line 4 "algorithm/mo_algorithm.hpp"
#include <cmath>

#line 7 "algorithm/mo_algorithm.hpp"

namespace ebi {

template <class IL, class IR, class DL, class DR, class O>
void mo_algorithm(const int &n, const std::vector<int> &l,
                  const std::vector<int> &r, const IL &insert_left,
                  const IR &insert_right, const DL &delete_left,
                  const DR &delete_right, const O &out) {
    const int q = l.size();
    const int block = n / std::max<int>(1, std::sqrt(n));
    std::vector<int> order(q, 0);
    iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int i, int j) {
        int bi = l[i] / block;
        int bj = l[j] / block;
        return bi != bj ? bi < bj : bi & 1 ? r[i] > r[j] : r[i] < r[j];
    });
    int nl = 0, nr = 0;
    for (auto i : order) {
        while (l[i] < nl) insert_left(--nl);
        while (nr < r[i]) insert_right(nr++);
        while (nl < l[i]) delete_left(nl++);
        while (r[i] < nr) delete_right(--nr);
        out(i);
    }
    return;
}

}  // namespace ebi
#line 2 "data_structure/compress.hpp"

#line 4 "data_structure/compress.hpp"
#include <cassert>
#line 6 "data_structure/compress.hpp"

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

    void build() {
        std::sort(cp.begin(), cp.end());
        cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    }

    void add(const T &val) {
        cp.emplace_back(val);
    }

    int get(const T &val) const {
        return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin();
    }

    int size() const {
        return cp.size();
    }

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi
#line 2 "data_structure/fenwick_tree.hpp"

#line 5 "data_structure/fenwick_tree.hpp"

namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi
#line 12 "test/data_structure/Static_Range_Inversion_Query.test.cpp"

using u64 = std::uint64_t;

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    std::vector<int> l(q), r(q);
    ebi::compress<int> cp;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        cp.add(a[i]);
    }
    cp.build();
    for (int i = 0; i < n; i++) {
        a[i] = cp.get(a[i]);
    }
    for (int i = 0; i < q; i++) {
        std::cin >> l[i] >> r[i];
    }
    ebi::fenwick_tree<u64> fw(cp.size());
    std::vector<u64> ans(q);
    u64 ret = 0;
    const auto insert_left = [&](int l) -> void {
        ret += fw.prefix_sum(a[l]);
        fw.add(a[l], 1);
    };
    const auto insert_right = [&](int r) -> void {
        ret += fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], 1);
    };
    const auto delete_left = [&](int l) -> void {
        ret -= fw.prefix_sum(a[l]);
        fw.add(a[l], -1);
    };
    const auto delete_right = [&](int r) -> void {
        ret -= fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], -1);
    };
    const auto out = [&](int i) -> void { ans[i] = ret; };
    ebi::mo_algorithm(n, l, r, insert_left, insert_right, delete_left,
                      delete_right, out);
    for (auto val : ans) {
        std::cout << val << '\n';
    }
}
Back to top page