matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/yosupo/static_range_inversions_query-mo_rollback.test.cpp
- View this file on GitHub
- Last update: 2024-07-22 18:41:16+09:00
- Problem: https://judge.yosupo.jp/problem/static_range_inversions_query
Code
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#include "include/mtl/compress_int.hpp"
#include "include/mtl/mo.hpp"
#include "include/mtl/lazy_segment_tree.hpp"
#include "include/mtl/monoid.hpp"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr int N = 1e5;
int sum(int a, int b) { return a+b; }
int e() { return 0; }
using sm = Monoid<int,sum,e>;
using P = pair<int,int>;
sm mapping(P c, sm x) {
return x.val()*c.first + c.second;
}
P composition(P l, P r) {
return {l.first*r.first, l.second*r.first + r.second};
}
P Id() { return {1,0}; }
struct um {
P x;
um() : x(Id()) {}
um(P x) : x(x) {}
um& operator*=(const um& rhs) {
x = composition(x, rhs.x);
return *this;
}
sm act(const sm& s) const {
return mapping(x, s);
}
};
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin>>A[i];
}
auto id = Compressor<int>::compress(A.begin(), A.end());
auto k = id.size();
MoSolver mo;
for (int i = 0; i < q; i++) {
int l,r; cin>>l>>r;
mo.add_segment(l, r);
}
SegmentTreebase<sm, um> D(k);
vector<lint> ans(q, -1);
lint inv_sum = 0;
stack<int> hist;
lint saved_inv_sum = 0;
int size = 0;
auto _pushl = [&](int i) {
int vi = id[A[i]];
auto count = D.query(0, vi).val();
assert(count <= size);
inv_sum += count;
hist.push(vi);
D.update(vi, make_pair(1,1));
size++;
};
auto _pushr = [&](int i) {
int vi = id[A[i]];
auto count = D.query(vi+1, k).val();
assert(count <= size);
inv_sum += count;
hist.push(vi);
D.update(vi, make_pair(1,1));
size++;
};
// auto _popl = [&](int i) {
// int vi = id[A[i]];
// inv_sum -= D.query(0, vi).val();
// D.update(vi, make_pair(1,-1));
// };
// auto _popr = [&](int i) {
// int vi = id[A[i]];
// inv_sum -= D.query(vi+1, k).val();
// D.update(vi, make_pair(1,-1));
// };
auto rem = [&](int t) {
ans[t] = inv_sum;
};
// mo.solve(_pushl, _pushr, _popl, _popr, rem);
auto init = [&]() {
D.update(0, k, make_pair(0,0));
inv_sum = 0;
size = 0;
};
auto snapshot = [&]() {
hist = {};
saved_inv_sum = inv_sum;
};
auto rollback = [&]() {
size -= hist.size();
while (!hist.empty()) {
int vi = hist.top(); hist.pop();
D.update(vi, make_pair(1,-1));
}
inv_sum = saved_inv_sum;
};
mo.solve_rollback(_pushl, _pushr, rem, init, snapshot, rollback);
for (lint v : ans) cout << v << endl;
}
#line 1 "test/yosupo/static_range_inversions_query-mo_rollback.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#line 2 "include/mtl/compress_int.hpp"
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
template<class T, class MapContainer=std::unordered_map<T, int>>
class Compressor {
public:
using map_type = MapContainer;
private:
std::vector<T> vs;
public:
Compressor() = default;
template<typename It>
Compressor(It begin, It end) : vs(begin, end) {}
void clear() { vs.clear(); }
void add(T x) {
vs.push_back(x);
}
template<typename It>
void add(It begin, It end) {
vs.insert(vs.end(), begin, end);
}
map_type release() {
std::sort(vs.begin(), vs.end());
vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
map_type mp;
mp.reserve(vs.size());
int k = 0;
for (auto v : vs) mp[v] = k++;
return mp;
}
std::pair<map_type, std::vector<T>> release_tie() {
return std::make_pair(release(), std::move(vs));
}
template<typename It>
static map_type compress(It begin, It end) {
return Compressor(begin, end).release();
}
};
#line 3 "include/mtl/mo.hpp"
#include <numeric>
#include <cmath>
#include <tuple>
#line 7 "include/mtl/mo.hpp"
#include <iostream>
#include <cassert>
/**
* @brief Mo's algorithm: solve offline segment queries on a sequence
* @note This implementation is optimized by noshi's idea
* complexity of N sqrt(Q) + O(N).
* - 定数倍が最適な Mo's Algorithm. noshi91のメモ. 2023/04/13.
* https://noshi91.hatenablog.com/entry/2023/04/13/224811
* @note Mo's algorithm with rollback is based on snuke's idea
* - Mo's algorithm とその上位互換の話. あなたは嘘つきですかと聞かれたら「YES」と答えるブログ. 2016/07/01.
* https://snuke.hatenablog.com/entry/2016/07/01/000000
*/
struct MoSolver {
std::vector<std::tuple<int, int, int>> segs;
int q = 0;
void add_segment(int l, int r) {
assert(l <= r);
segs.emplace_back(q++, l, r);
}
void calc_mos_move(std::vector<int>& dst) const {
using std::get;
int n = 0;
for (auto s:segs)
n = std::max(n, get<2>(s));
auto rtq = std::sqrt(q);
int b = std::ceil((double)n / rtq);
auto bf = b-b/2;
auto get_bo = [&](int x) {
if (x < bf) return 0;
return (x-bf)/b+1;
};
auto EvenComp = [&](int u, int v) {
auto &s = segs[u], &t = segs[v];
auto ls = get<1>(s), rs = get<2>(s), lt = get<1>(t), rt = get<2>(t);
auto bs = ls / b, bt = lt / b;
return bs != bt ? ls < lt : (bs%2==0 ? rs < rt : rs > rt);
};
auto OddComp = [&](int u, int v) {
auto &s = segs[u], &t = segs[v];
auto ls = get<1>(s), rs = get<2>(s), lt = get<1>(t), rt = get<2>(t);
auto bs = get_bo(ls), bt = get_bo(lt);
return bs != bt ? ls < lt : (bs%2==0 ? rs < rt : rs > rt);
};
auto& IE = dst;
IE.resize(q);
std::iota(IE.begin(), IE.end(), 0);
std::sort(IE.begin(), IE.end(),
EvenComp);
auto IO = IE;
std::sort(IO.begin(), IO.end(),
OddComp);
auto move_distance = [&](const std::vector<int>& ids) {
long long d = 0;
for (int i = 0; i < q-1; i++) {
int j = ids[i], k = ids[i+1];
d += std::abs(get<1>(segs[j]) - get<1>(segs[k]));
d += std::abs(get<2>(segs[j]) - get<2>(segs[k]));
}
return d;
};
if (move_distance(IE) > move_distance(IO))
dst = std::move(IO); // IE is reference of dst
}
template<class PUSH_L, class PUSH_R, class POP_L, class POP_R, class REM>
void solve(PUSH_L pushl, PUSH_R pushr, POP_L popl, POP_R popr, REM rem) const {
if (q == 0) return;
std::vector<int> I;
calc_mos_move(I);
int _l = 0, _r = 0;
for (int i:I) {
int t,l,r;
std::tie(t,l,r) = segs[i];
while (l < _l)
pushl(--_l);
while (_r < r)
pushr(_r++);
while (_l < l)
popl(_l++);
while (r < _r)
popr(--_r);
rem(t);
}
}
template<class Block, class Bend>
long long calc_mos_rollback_move(std::vector<int>& idx, std::vector<std::pair<int,int>>& blocks, Block block, Bend bend) const {
std::sort(idx.begin(), idx.end(), [&](auto a, auto b) {
auto [ta, la, ra] = segs[a];
auto [tb, lb, rb] = segs[b];
auto ba = block(la), bb = block(lb);
return ba != bb ? la < lb : ra < rb;
});
long long dist = 0;
int cb = -1;
int _l = 0, _r = 0;
for (size_t i = 0; i < idx.size(); i++) {
auto [t,l,r] = segs[idx[i]];
auto bi = block(l);
auto be = bend(bi);
blocks[i] = std::make_pair(bi, be);
if (bi != cb) {
_r = be;
cb = bi;
}
dist += r-_r;
_r = r;
_l = be;
dist += _l-l;
}
return dist;
}
template<class PUSH_L, class PUSH_R, class REM,
class INIT, class SNAPSHOT, class ROLLBACK>
void solve_rollback(PUSH_L pushl, PUSH_R pushr, REM rem,
INIT init, SNAPSHOT snapshot, ROLLBACK rollback) const {
if (q == 0) return;
int n = 0;
for (auto s:segs)
n = std::max(n, std::get<2>(s));
// * (2|xi-c|+b/2)q, |xi-c| < b/2, (mean |xi-c| = b/4) -> bq
// * min bq + n^2/b,
// from AMGM, bq = n^2/b => b^2 = n^2 /q => b = n / sqrt(q)
// * F = (bq + n^2/b)/2
// = bq
// = n sqrt(q)
const int b = std::ceil((double)n / std::sqrt(q));
std::vector<int> J;
for (int i = 0; i < q; i++) {
auto [t,l,r] = segs[i];
if (r-l < b) {
init();
for (int j = l; j < r; j++)
pushr(j);
rem(t);
} else {
J.push_back(i);
}
}
std::vector<std::pair<int,int>> B(J.size());
{
auto& b_even = B;
auto block_even = [&](int x) {
return x / b;
};
auto bend_even = [&](int bi) {
return (bi+1)*b;
};
auto dist_e = calc_mos_rollback_move(J, b_even, block_even, bend_even);
auto K = J;
auto b_odd = B;
const auto bf = b-b/2;
auto block_odd = [&](int x) {
return x < bf ? 0 : (x-bf)/b+1;
};
auto bend_odd = [&](int bi) {
return bf+bi*b;
};
auto dist_o = calc_mos_rollback_move(K, b_odd, block_odd, bend_odd);
if (dist_e > dist_o) {
J = std::move(K);
B = std::move(b_odd);
}
}
int cb = -1;
int _l = 0, _r = 0;
for (auto it = J.begin(); it != J.end(); ++it) {
auto [t,l,r] = segs[*it];
auto [bi,be] = B[it-J.begin()];
if (bi != cb) {
init();
_r = be;
cb = bi;
}
assert(_r <= r);
while (_r < r) {
pushr(_r++);
}
snapshot();
_l = be;
assert(l <= _l);
assert(_l-l <= b);
while (l < _l) {
pushl(--_l);
}
rem(t);
rollback();
}
}
};
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#line 4 "include/mtl/bit_manip.hpp"
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif
namespace bm {
/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
return std::popcount(x);
#else
return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_zero(x);
#else
return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_one(x);
#else
return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
constexpr uint64_t hmask = 0x8080808080808080ull;
constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
auto a = x & hmask;
auto b = x & lmask;
b = hmask - b;
b = ~b;
auto c = (a | b) & hmask;
c *= 0x0002040810204081ull;
return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
if (x & 0x80)
return 8;
uint64_t p = uint64_t(x) * 0x0101010101010101ull;
p -= 0x8040201008040201ull;
p = ~p & 0x8080808080808080ull;
p = (p >> 7) * 0x0101010101010101ull;
p >>= 56;
return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
assert(x != 0);
return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
assert(x != 0);
return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_zero(x);
#else
if (x == 0)
return 64;
auto i = mssb8(summary(x));
auto j = mssb8(bextr(x, 8 * i, 8));
return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_one(x);
#else
return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
return clo(x);
}
inline constexpr unsigned clz8(uint8_t x) {
return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
return x;
}
/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::has_single_bit(x);
#else
return x != 0 && (x & (x - 1)) == 0;
#endif
}
/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::bit_width(x);
#else
return 64 - clz(x);
#endif
}
/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_ceil(x);
#else
if (x == 0) return 1;
return 1ull << bit_width(x - 1);
#endif
}
/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_floor(x);
#else
if (x == 0) return 0;
return 1ull << (bit_width(x) - 1);
#endif
}
} // namespace bm
#line 3 "include/mtl/lazy_segment_tree.hpp"
// #include "monoid.hpp"
#include <cstddef>
#include <utility>
#line 7 "include/mtl/lazy_segment_tree.hpp"
#include <stack>
#line 9 "include/mtl/lazy_segment_tree.hpp"
#if __cpp_concepts >= 202002L
#include <concepts>
template<typename M>
concept LazySegmentTreeMonoid = requires (M m) {
{m * m} -> std::same_as<M>;
};
template<typename A, typename M>
concept LazySegmentTreeOperatorMonoid = requires(A a, M m) {
{a *= a} -> std::same_as<A&>;
{a.act(m)} -> std::same_as<M>;
};
#endif
template <typename M, typename A>
#if __cpp_concepts >= 202002L
requires LazySegmentTreeMonoid<M> &&
LazySegmentTreeOperatorMonoid<A,M>
#endif
class SegmentTreebase {
private:
size_t size_;
std::vector<std::pair<M, A>> tree_;
std::vector<size_t> ids_;
public:
explicit SegmentTreebase(size_t size) :
size_(1ull<<(64-bm::clz(size-1))),
tree_(size_*2) {
ids_.reserve((64-bm::clz(size-1))*2);
}
template <typename Iter>
explicit SegmentTreebase(Iter begin, Iter end)
: SegmentTreebase(std::distance(begin, end)) {
static_assert(std::is_convertible<typename std::iterator_traits<Iter>::value_type, M>::value, "");
for (auto it = begin; it != end; ++it) {
tree_[size_ + it - begin].first = *it;
}
for (size_t i = size_-1; i > 0; i--) {
tree_[i].first = tree_[i*2].first * tree_[i*2+1].first;
}
}
inline void range_update(size_t l, size_t r, const A& e) {
assert(l <= r);
assert(r <= size_);
if (l == r) return;
_lazy_propagation(l, r);
for (size_t _l=l+size_, _r=r+size_; _l<_r; _l>>=1, _r>>=1) {
if (_l&1)
tree_[_l++].second *= e;
if (_r&1)
tree_[--_r].second *= e;
}
for (auto id : ids_) {
_propagate(id*2);
_propagate(id*2+1);
tree_[id].first = tree_[id*2].first * tree_[id*2+1].first;
}
}
inline void update(size_t l, size_t r, const A& e) {
range_update(l, r, e);
}
inline void update(size_t i, const A& e) {
range_update(i, i+1, e);
}
template<typename T>
inline void set(size_t i, T&& e) {
_lazy_propagation(i, i+1);
int u = i+size_;
tree_[u].first = M(std::forward<T>(e));
u >>= 1;
while (u > 0) {
tree_[u].first = tree_[u*2].first * tree_[u*2+1].first;
u >>= 1;
}
}
inline M query(size_t l, size_t r) {
_lazy_propagation(l, r);
M lhs,rhs;
for (size_t _l=l+size_, _r=r+size_; _l<_r; _l>>=1, _r>>=1) {
if (_l&1) {
_propagate(_l);
lhs = lhs * tree_[_l].first;
++_l;
}
if (_r&1) {
--_r;
_propagate(_r);
rhs = tree_[_r].first * rhs;
}
}
return lhs * rhs;
}
/// Alias for query(l, r)
M prod(size_t l, size_t r) {
return query(l, r);
}
inline const M& get(size_t index) {
_lazy_propagation(index, index+1);
auto l = index+size_;
_propagate(l);
return tree_[l].first;
}
private:
void _set_ids(size_t l, size_t r) {
ids_.clear();
auto _l=l+size_, _r=r+size_;
auto lth = _l/(_l&(-_l))/2;
auto rth = _r/(_r&(-_r))/2;
for (; _l<_r; _l>>=1, _r>>=1) {
if (_r <= rth) ids_.push_back(_r);
if (_l <= lth) ids_.push_back(_l);
}
for (; _l>0; _l>>=1)
ids_.push_back(_l);
}
inline void _propagate(size_t id) {
A& e = tree_[id].second;
tree_[id].first = e.act(tree_[id].first);
if (id < size_) {
tree_[id*2].second *= e;
tree_[id*2+1].second *= e;
}
tree_[id].second = A();
}
void _lazy_propagation(size_t l, size_t r) {
if (l == r) return;
_set_ids(l, r);
for (auto it = ids_.rbegin(); it != ids_.rend(); ++it)
_propagate(*it);
}
public:
template<class F>
size_t max_right(size_t begin, size_t end, F f) {
if (begin == end) return end;
M p;
std::stack<std::pair<size_t, M>> rps;
auto l = size_ + begin;
auto r = size_ + end;
_lazy_propagation(begin, end);
auto access = [&](size_t i) {
_propagate(i);
return tree_[i].first;
};
while (l < r and f(p * access(l))) {
if (l&1) p = p * tree_[l++].first;
if (r&1) {
rps.emplace(r, access(r-1));
r--;
}
l>>=1; r>>=1;
}
if (l >= r) {
while (rps.size()) {
auto& [r, rp] = rps.top();
if (!f(p * rp)) {
l = r-1;
break;
}
p = p * rp;
rps.pop();
}
if (rps.empty()) return end;
}
while (l < size_) {
assert(!f(p * access(l)));
l <<= 1;
auto pl = access(l);
if (f(p * pl)) {
p = p * pl;
l++;
}
}
return l - size_;
}
template<bool (*F)(M)>
size_t max_right(size_t begin, size_t end) {
return max_right(begin, end, [](M x) { return F(x); });
}
template<class F>
size_t min_left(size_t begin, size_t end, F f) {
if (end == begin) return begin;
M p;
std::stack<std::pair<size_t, M>> lps;
auto l = size_ + begin;
auto r = size_ + end;
_lazy_propagation(begin, end);
auto access = [&](size_t i) {
_propagate(i);
return tree_[i].first;
};
while (l < r and f(access(r-1) * p)) {
if (l&1) {
lps.emplace(l, access(l));
l++;
}
if (r&1) p = tree_[r-1].first * p;
l>>=1; r>>=1;
}
if (l >= r) {
while (lps.size()) {
auto& [l, lp] = lps.top();
if (!f(lp * p)) {
r = l+1;
break;
}
p = lp * p;
lps.pop();
}
if (lps.empty()) return begin;
}
while (r <= size_) {
assert(!f(access(r-1) * p));
r <<= 1;
auto pr = access(r-1);
if (f(pr * p)) {
p = pr * p;
--r;
}
}
return r - size_;
}
template<bool (*F)(M)>
size_t min_left(size_t begin, size_t end) {
return min_left(begin, [](M x) { return F(x); });
}
};
#line 3 "include/mtl/monoid.hpp"
#if __cpp_concepts >= 202002L
#include <concepts>
#endif
template<class T, T (*op)(T, T), T (*e)()>
struct Monoid {
T x;
Monoid() : x(e()) {}
template<class... Args>
Monoid(Args&&... args) : x(std::forward<Args>(args)...) {}
Monoid operator*(const Monoid& rhs) const {
return Monoid(op(x, rhs.x));
}
const T& val() const {
return x;
}
};
struct VoidMonoid {
VoidMonoid() {}
VoidMonoid operator*(const VoidMonoid& rhs) const {
return VoidMonoid();
}
};
#if __cpp_concepts >= 202002L
template<class T>
concept IsMonoid = requires (T m) {
{ m * m } -> std::same_as<T>;
};
#endif
template<class T, T (*op)(T, T), T (*e)()>
struct CommutativeMonoid : public Monoid<T, op, e> {
using Base = Monoid<T, op, e>;
CommutativeMonoid(T x=e()) : Base(x) {}
CommutativeMonoid operator+(const CommutativeMonoid& rhs) const {
return CommutativeMonoid(*this * rhs);
}
};
#if __cpp_concepts >= 202002L
template<class T>
concept IsCommutativeMonoid = requires (T m) {
{ m + m } -> std::same_as<T>;
};
#endif
template<class S, class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct OperatorMonoid {
F f;
OperatorMonoid() : f(id()) {}
template<class... Args>
OperatorMonoid(Args&&... args) : f(std::forward<Args>(args)...) {}
OperatorMonoid& operator*=(const OperatorMonoid& rhs) {
f = composition(rhs.f, f);
return *this;
}
S act(const S& s) const {
return mapping(f, s);
}
};
struct VoidOperatorMonoid {
VoidOperatorMonoid() {}
VoidOperatorMonoid& operator*=(const VoidOperatorMonoid& rhs) {
return *this;
}
template<class T>
T act(const T& s) const {
return s;
}
};
#if __cpp_concepts >= 202002L
template<class F, class S>
concept IsOperatorMonoid = requires (F f, S s) {
{ f *= f } -> std::same_as<F&>;
{ f.act(s) } -> std::same_as<S>;
};
#endif
#line 6 "test/yosupo/static_range_inversions_query-mo_rollback.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr int N = 1e5;
int sum(int a, int b) { return a+b; }
int e() { return 0; }
using sm = Monoid<int,sum,e>;
using P = pair<int,int>;
sm mapping(P c, sm x) {
return x.val()*c.first + c.second;
}
P composition(P l, P r) {
return {l.first*r.first, l.second*r.first + r.second};
}
P Id() { return {1,0}; }
struct um {
P x;
um() : x(Id()) {}
um(P x) : x(x) {}
um& operator*=(const um& rhs) {
x = composition(x, rhs.x);
return *this;
}
sm act(const sm& s) const {
return mapping(x, s);
}
};
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin>>A[i];
}
auto id = Compressor<int>::compress(A.begin(), A.end());
auto k = id.size();
MoSolver mo;
for (int i = 0; i < q; i++) {
int l,r; cin>>l>>r;
mo.add_segment(l, r);
}
SegmentTreebase<sm, um> D(k);
vector<lint> ans(q, -1);
lint inv_sum = 0;
stack<int> hist;
lint saved_inv_sum = 0;
int size = 0;
auto _pushl = [&](int i) {
int vi = id[A[i]];
auto count = D.query(0, vi).val();
assert(count <= size);
inv_sum += count;
hist.push(vi);
D.update(vi, make_pair(1,1));
size++;
};
auto _pushr = [&](int i) {
int vi = id[A[i]];
auto count = D.query(vi+1, k).val();
assert(count <= size);
inv_sum += count;
hist.push(vi);
D.update(vi, make_pair(1,1));
size++;
};
// auto _popl = [&](int i) {
// int vi = id[A[i]];
// inv_sum -= D.query(0, vi).val();
// D.update(vi, make_pair(1,-1));
// };
// auto _popr = [&](int i) {
// int vi = id[A[i]];
// inv_sum -= D.query(vi+1, k).val();
// D.update(vi, make_pair(1,-1));
// };
auto rem = [&](int t) {
ans[t] = inv_sum;
};
// mo.solve(_pushl, _pushr, _popl, _popr, rem);
auto init = [&]() {
D.update(0, k, make_pair(0,0));
inv_sum = 0;
size = 0;
};
auto snapshot = [&]() {
hist = {};
saved_inv_sum = inv_sum;
};
auto rollback = [&]() {
size -= hist.size();
while (!hist.empty()) {
int vi = hist.top(); hist.pop();
D.update(vi, make_pair(1,-1));
}
inv_sum = saved_inv_sum;
};
mo.solve_rollback(_pushl, _pushr, rem, init, snapshot, rollback);
for (lint v : ans) cout << v << endl;
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | example_00 |
AC |
6 ms | 3 MB |
| g++ | max_00 |
AC |
19314 ms | 16 MB |
| g++ | max_01 |
AC |
18863 ms | 16 MB |
| g++ | max_02 |
AC |
19122 ms | 16 MB |
| g++ | random_00 |
AC |
2644 ms | 8 MB |
| g++ | random_01 |
AC |
5964 ms | 11 MB |
| g++ | random_02 |
AC |
7381 ms | 10 MB |
| g++ | small_a_00 |
AC |
9273 ms | 9 MB |
| g++ | small_n_00 |
AC |
26 ms | 4 MB |
| g++ | small_n_01 |
AC |
96 ms | 7 MB |
| g++ | small_n_02 |
AC |
68 ms | 6 MB |
| g++ | small_n_03 |
AC |
48 ms | 5 MB |
| g++ | small_n_04 |
AC |
24 ms | 4 MB |
| clang++ | example_00 |
AC |
6 ms | 3 MB |
| clang++ | max_00 |
AC |
25861 ms | 16 MB |
| clang++ | max_01 |
AC |
25184 ms | 16 MB |
| clang++ | max_02 |
AC |
25337 ms | 16 MB |
| clang++ | random_00 |
AC |
3512 ms | 8 MB |
| clang++ | random_01 |
AC |
7796 ms | 10 MB |
| clang++ | random_02 |
AC |
9927 ms | 10 MB |
| clang++ | small_a_00 |
AC |
12505 ms | 9 MB |
| clang++ | small_n_00 |
AC |
26 ms | 4 MB |
| clang++ | small_n_01 |
AC |
103 ms | 7 MB |
| clang++ | small_n_02 |
AC |
71 ms | 6 MB |
| clang++ | small_n_03 |
AC |
52 ms | 5 MB |
| clang++ | small_n_04 |
AC |
27 ms | 4 MB |