sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query" #include <bits/stdc++.h> #include "../../data-structure/fenwick_tree.hpp" #include "../../misc/compress.hpp" #include "../../misc/mo.hpp" using namespace std; using ll = long long; struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; int main() { ios_base::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]; A = Compress<int>(A).compress(A); Mo mo(N); for (int i = 0; i < Q; ++i) { int l, r; cin >> l >> r; mo.query(l, r); } FenwickTree<AddMonoid> fw(N); ll res = 0; vector<ll> ans(Q); auto exl = [&](int i) { res += fw.prefix_fold(A[i]); fw.update(A[i], 1); }; auto shl = [&](int i) { res -= fw.prefix_fold(A[i]); fw.update(A[i], -1); }; auto exr = [&](int i) { res += fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1); fw.update(A[i], 1); }; auto shr = [&](int i) { res -= fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1); fw.update(A[i], -1); }; auto out = [&](int i) { ans[i] = res; }; mo.run(exl, shl, exr, shr, out); for (auto& x : ans) cout << x << "\n"; }
#line 1 "test/yosupo/static_range_inversions_query.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query" #include <bits/stdc++.h> #line 4 "data-structure/fenwick_tree.hpp" template <typename M> class FenwickTree { using T = M::T; public: FenwickTree() = default; explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {} T prefix_fold(int i) const { T ret = M::id(); for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]); return ret; } void update(int i, const T& x) { for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x); } int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); } template <typename Compare> int lower_bound(const T& x, Compare cmp) const { if (!cmp(M::id(), x)) return 0; int k = 1; while (k * 2 <= n) k <<= 1; int i = 0; T v = M::id(); for (; k > 0; k >>= 1) { if (i + k > n) continue; T nv = M::op(v, data[i + k]); if (cmp(nv, x)) { v = nv; i += k; } } return i + 1; } private: int n; std::vector<T> data; }; #line 4 "misc/compress.hpp" /** * @brief Coordinate Compression */ template <typename T> class Compress { public: Compress() = default; explicit Compress(const std::vector<T>& vs) : xs(vs) { std::ranges::sort(xs); xs.erase(std::ranges::unique(xs).begin(), xs.end()); } int compress(const T& x) const { return std::ranges::lower_bound(xs, x) - xs.begin(); } std::vector<int> compress(const std::vector<T>& vs) const { std::vector<int> res(vs.size()); std::ranges::transform(vs, res.begin(), [&](const T& x) { return compress(x); }); return res; } T decompress(int i) const { return xs[i]; } int size() const { return xs.size(); } private: std::vector<T> xs; }; #line 5 "misc/mo.hpp" class Mo { public: Mo() = default; explicit Mo(int n) : n(n), cnt(0) {} void query(int l, int r) { queries.emplace_back(cnt++, l, r); } template <typename ExL, typename ShL, typename ExR, typename ShR, typename Out> void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out) { int s = sqrt(n); std::ranges::sort( queries, {}, [&](auto& q) { return std::make_pair(q.l / s, q.r); }); int curL = 0, curR = 0; for (auto [id, l, r] : queries) { while (curL > l) exl(--curL); while (curR < r) exr(curR++); while (curL < l) shl(curL++); while (curR > r) shr(--curR); out(id); } } private: struct Query { int id, l, r; }; int n, cnt; std::vector<Query> queries; }; #line 8 "test/yosupo/static_range_inversions_query.test.cpp" using namespace std; using ll = long long; struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; int main() { ios_base::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]; A = Compress<int>(A).compress(A); Mo mo(N); for (int i = 0; i < Q; ++i) { int l, r; cin >> l >> r; mo.query(l, r); } FenwickTree<AddMonoid> fw(N); ll res = 0; vector<ll> ans(Q); auto exl = [&](int i) { res += fw.prefix_fold(A[i]); fw.update(A[i], 1); }; auto shl = [&](int i) { res -= fw.prefix_fold(A[i]); fw.update(A[i], -1); }; auto exr = [&](int i) { res += fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1); fw.update(A[i], 1); }; auto shr = [&](int i) { res -= fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1); fw.update(A[i], -1); }; auto out = [&](int i) { ans[i] = res; }; mo.run(exl, shl, exr, shr, out); for (auto& x : ans) cout << x << "\n"; }