C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title その他/Mo's algorithm * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query */ #include <algorithm> #include <iostream> #include <iterator> #include <vector> #include "emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" #include "emthrm/misc/mo.hpp" std::vector<int> a; long long inv = 0; int l = 0, r = 0, m; constexpr int M = 100000; emthrm::FenwickTree<int> bit(M); void emthrm::Mo::add(const int idx) const { if (idx + 1 == l) { inv += bit.sum(0, a[idx]); --l; } else if (idx == r) { inv += bit.sum(a[idx] + 1, m); ++r; } bit.add(a[idx], 1); } void emthrm::Mo::del(const int idx) const { if (idx == l) { inv -= bit.sum(0, a[idx]); ++l; } else if (idx + 1 == r) { inv -= bit.sum(a[idx] + 1, m); --r; } bit.add(a[idx], -1); } int main() { int n, q; std::cin >> n >> q; a.resize(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::vector<int> tmp = a; std::sort(tmp.begin(), tmp.end()); tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end()); m = tmp.size(); for (int i = 0; i < n; ++i) { a[i] = std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), a[i])); } std::vector<int> ls(q), rs(q); for (int i = 0; i < q; ++i) { std::cin >> ls[i] >> rs[i]; } emthrm::Mo mo(ls, rs); std::vector<long long> ans(q); for (int i = 0; i < q; ++i) { const int idx = mo.process(); ans[idx] = inv; } for (int i = 0; i < q; ++i) { std::cout << ans[i] << '\n'; } return 0; }
#line 1 "test/misc/mo.test.cpp" /* * @title その他/Mo's algorithm * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query */ #include <algorithm> #include <iostream> #include <iterator> #include <vector> #line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" #include <bit> #line 6 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" namespace emthrm { template <typename Abelian> struct FenwickTree { explicit FenwickTree(const int n, const Abelian ID = 0) : n(n), ID(ID), data(n, ID) {} void add(int idx, const Abelian val) { for (; idx < n; idx |= idx + 1) { data[idx] += val; } } Abelian sum(int idx) const { Abelian res = ID; for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) { res += data[idx]; } return res; } Abelian sum(const int left, const int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= ID) [[unlikely]] return 0; int res = 0; for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1; mask > 0; mask >>= 1) { const int idx = res + mask - 1; if (idx < n && data[idx] < val) { val -= data[idx]; res += mask; } } return res; } private: const int n; const Abelian ID; std::vector<Abelian> data; }; } // namespace emthrm #line 1 "include/emthrm/misc/mo.hpp" #line 5 "include/emthrm/misc/mo.hpp" #include <cmath> #include <numeric> #line 8 "include/emthrm/misc/mo.hpp" namespace emthrm { struct Mo { explicit Mo(const std::vector<int>& ls, const std::vector<int>& rs) : n(ls.size()), ptr(0), nl(0), nr(0), ls(ls), rs(rs) { const int width = std::round(std::sqrt(n)); order.resize(n); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [&ls, &rs, width](const int a, const int b) -> bool { if (ls[a] / width != ls[b] / width) return ls[a] < ls[b]; return (ls[a] / width) & 1 ? rs[a] < rs[b] : rs[a] > rs[b]; }); } int process() { if (ptr == n) [[unlikely]] return -1; const int id = order[ptr++]; while (ls[id] < nl) add(--nl); while (nr < rs[id]) add(nr++); while (nl < ls[id]) del(nl++); while (rs[id] < nr) del(--nr); return id; } void add(const int idx) const; void del(const int idx) const; private: const int n; int ptr, nl, nr; std::vector<int> ls, rs, order; }; } // namespace emthrm #line 14 "test/misc/mo.test.cpp" std::vector<int> a; long long inv = 0; int l = 0, r = 0, m; constexpr int M = 100000; emthrm::FenwickTree<int> bit(M); void emthrm::Mo::add(const int idx) const { if (idx + 1 == l) { inv += bit.sum(0, a[idx]); --l; } else if (idx == r) { inv += bit.sum(a[idx] + 1, m); ++r; } bit.add(a[idx], 1); } void emthrm::Mo::del(const int idx) const { if (idx == l) { inv -= bit.sum(0, a[idx]); ++l; } else if (idx + 1 == r) { inv -= bit.sum(a[idx] + 1, m); --r; } bit.add(a[idx], -1); } int main() { int n, q; std::cin >> n >> q; a.resize(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::vector<int> tmp = a; std::sort(tmp.begin(), tmp.end()); tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end()); m = tmp.size(); for (int i = 0; i < n; ++i) { a[i] = std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), a[i])); } std::vector<int> ls(q), rs(q); for (int i = 0; i < q; ++i) { std::cin >> ls[i] >> rs[i]; } emthrm::Mo mo(ls, rs); std::vector<long long> ans(q); for (int i = 0; i < q; ++i) { const int idx = mo.process(); ans[idx] = inv; } for (int i = 0; i < q; ++i) { std::cout << ans[i] << '\n'; } return 0; }