This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#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'; } }