Src/Sequence/InversionNumber.hpp

• View this file on GitHub
• Last update: 2024-07-09 02:49:52+09:00
• Include: #include "Src/Sequence/InversionNumber.hpp"

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AOJ/ALDS1_5_D.test.cpp
• Test/AtCoder/abc261_f.test.cpp
• ABC296-F Simultaneous Swap (互換は奇数回の隣接swap) (Test/AtCoder/abc296_f.test.cpp)

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <cassert>
#include <iterator>
#include <type_traits>
#include <vector>

namespace zawa {

template <class InputIterator>
u64 InversionNumber(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> u64 {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        u64 res{rec(rec, L, M) + rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res += M - i;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

template <class InputIterator>
bool InversionParity(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> bool {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        bool res{rec(rec, L, M) != rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res ^= (M - i) & 1;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

} // namespace zawa

#line 2 "Src/Sequence/InversionNumber.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/InversionNumber.hpp"

#include <cassert>
#include <iterator>
#include <type_traits>
#include <vector>

namespace zawa {

template <class InputIterator>
u64 InversionNumber(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> u64 {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        u64 res{rec(rec, L, M) + rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res += M - i;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

template <class InputIterator>
bool InversionParity(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> bool {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        bool res{rec(rec, L, M) != rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res ^= (M - i) & 1;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

} // namespace zawa

Back to top page