1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#pragma once


#include <cstdint><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <iterator><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <algorithm><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "snippet/aliases.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"

#include "iterable/compressed.hpp"

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

namespace uni {

template<const bool STRICT = true, class T = std::int64_t>
struct inversion {
    template<std::input_iterator I, std::sentinel_for<I> S>
    static inline T count(I first, S last) noexcept(NO_EXCEPT) {
        const internal::size_t n = std::distance(first, last);
        const auto [ min, max ] = std::minmax_element(first, last);<--- Shadow variable<--- Shadow variable
        const auto m = *max - *min + 1;

        fenwick_tree<actions::range_sum<T>> cnt(m);

        T res = 0;
        {
            internal::size_t i = 0;
            I itr = first;
            for(; i < n; ++i, ++itr) {
                res += cnt(*itr - *min + STRICT, m).fold().val();
                cnt[*itr - *min] += 1;
            }
        }

        return res;
    }

    template<std::ranges::input_range R>
    static inline T count(R&& range) noexcept(NO_EXCEPT) {
        return inversion::count(ALL(range));
    }

    template<std::input_iterator I, std::sentinel_for<I> S>
    static inline T count_with_compression(I first, S last) noexcept(NO_EXCEPT) {
        compressed<typename std::iterator_traits<I>::value_type> comp(first, last);
        return inversion::count(comp);
    }

    template<std::ranges::input_range R>
    static inline T count_with_compression(R&& range) noexcept(NO_EXCEPT) {
        return inversion::count_with_compression(ALL(range));
    }
};


} // namespace uni