rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: dp/test/inversion_number.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D"

#include <iostream>
#include <map>
#include <set>

#include "../../random/base.hpp"
#include "../inversion_number.hpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto&& e : a) std::cin >> e;
    long long ans1 = inversion_number<int>(a);
    // a -> b への単射 f を作成
    std::map<int, long long> f;
    std::set<long long> seen;
    for (int i = 0; i < n; i++) {
        if (f.count(a[i]) > 0) continue;
        while (true) {
            auto val = rng_auto.rand_int();
            if (seen.count(val) == 0) {
                f[a[i]] = val;
                seen.insert(val);
                break;
            }
        }
    }
    // a -> a_sorted の転倒数 (ans1) と
    // f(a) -> f(a_sorted) の転倒数 (ans2) が一致することを確認
    auto a_sorted = a;
    std::sort(a_sorted.begin(), a_sorted.end());
    std::vector<long long> b(n), b_sorted(n);
    for (int i = 0; i < n; i++) {
        b[i] = f[a[i]];
        b_sorted[i] = f[a_sorted[i]];
    }
    long long ans2 = inversion_number<long long>(b, b_sorted);
    assert(ans1 == ans2);
    std::cout << ans1 << '\n';
    return 0;
}
#line 1 "dp/test/inversion_number.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D"

#include <iostream>
#include <map>
#include <set>

#line 2 "random/base.hpp"

#include <cassert>
#include <chrono>
#include <cstdint>

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 8 "random/base.hpp"

template <bool auto_seed> struct Random {
    uint64_t x_seed;

    Random(uint64_t seed = 0) {
        if (auto_seed) {
            // set random seed
            assert(seed == 0);
            x_seed =
                std::chrono::steady_clock::now().time_since_epoch().count();
        } else {
            // set seed
            x_seed = seed;
        }
    }

    // http://xorshift.di.unimi.it/splitmix64.c
    // [0, 2^64 - 1]
    uint64_t rand_int() {
        uint64_t z = (x_seed += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    // [0, mod - 1]
    // rand_int() % mod だと mod が 2 べきでないときに偏る
    uint64_t rand_int(uint64_t mod) {
        assert(mod > 0);
        if ((mod & (mod - 1)) == 0) {
            // mod = 2^p
            // (mod - 1) = 0...01...1
            return rand_int() & (mod - 1);
        }
        // mod >= 3 (1 = 2^0, 2 = 2^1)
        int lg = topbit((unsigned long long)mod);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = rand_int() & mask;
            if (r < mod) return r;
        }
    }

    // [l, r]
    template <class T> T rand_int(T l, T r) {
        assert(l <= r);
        return T(l + rand_int(uint64_t(r - l + 1)));
    }

    // [0.0, 1.0]
    double rand_double() {
        uint64_t v = rand_int(1ULL << 63);
        return double(v) / ((1ULL << 63) - 1);
    }

    // [l, r]
    double rand_double(double l, double r) {
        assert(l <= r);
        return l + rand_double() * (r - l);
    }
};

using RandomFixed = Random<false>;
using RandomAuto = Random<true>;

RandomAuto rng_auto;
#line 2 "dp/inversion_number.hpp"

#include <algorithm>
#line 2 "data_structure/fenwick_tree.hpp"

#include <vector>
#line 5 "data_structure/fenwick_tree.hpp"

template <class T> struct FenwickTree {
    int n;
    std::vector<T> seg;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), seg(n + 1, 0) {}
    FenwickTree(std::vector<T>& arr) {
        n = int(arr.size());
        seg.resize(n + 1);
        for (int i = 0; i < n; i++) add(i, arr[i]);
    }
    // A[i] += x
    void add(int i, const T& x) {
        assert(0 <= i and i < n);
        i++;  // 1-indexed
        while (i <= n) {
            seg[i] += x;
            i += i & -i;
        }
    }
    // A[0] + ... + A[i - 1]
    T sum(int i) const {
        assert(0 <= i and i <= n);
        T s = T(0);
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    }
    // A[a] + ... + A[b - 1]
    T sum(int a, int b) const {
        assert(0 <= a and a <= b and b <= n);
        return sum(b) - sum(a);
    }
    // return A[i]
    T get(int i) const { return sum(i, i + 1); }
    // A[i] = x
    void set(int i, const T x) { add(i, x - get(i)); }

    std::vector<T> make_vector() {
        std::vector<T> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }
};
#line 5 "dp/inversion_number.hpp"

// a を sorted にするための隣接 swap の操作回数
template <class T> long long inversion_number(std::vector<T>& a) {
    auto za = a;
    std::sort(za.begin(), za.end());
    za.erase(std::unique(za.begin(), za.end()), za.end());
    const int m = (int)(za.size());
    FenwickTree<int> seg(m);
    long long res = 0;
    for (auto&& e : a) {
        int i = std::lower_bound(za.begin(), za.end(), e) - za.begin();
        res += seg.sum(i + 1, m);
        seg.add(i, 1);
    }
    return res;
}

// a -> b にするための隣接 swap の操作回数
template <class T>
long long inversion_number(std::vector<T>& a, std::vector<T>& b) {
    auto za = a;
    auto zb = b;
    std::sort(za.begin(), za.end());
    std::sort(zb.begin(), zb.end());
    assert(za == zb);
    za.erase(std::unique(za.begin(), za.end()), za.end());
    // a = [100, 1, 10, 1], b = [10, 1, 1, 100] (n = 4, m = 3)
    // a = [3, 1, 0, 2] を b = [0, 1, 2, 3] にするための操作回数に帰着する
    // g = [[1, 2], [0], [3]] になる
    const int n = (int)(a.size());
    const int m = (int)(za.size());
    std::vector<std::vector<int>> g(m);
    for (int i = 0; i < n; i++) {
        int index = std::lower_bound(za.begin(), za.end(), b[i]) - za.begin();
        g[index].push_back(i);
    }
    std::vector<int> g_offset(m, 0);
    FenwickTree<int> seg(n);
    long long res = 0;
    for (int i = 0; i < n; i++) {
        int index = std::lower_bound(za.begin(), za.end(), a[i]) - za.begin();
        int offset = g_offset[index];
        int a_pos = g[index][offset];
        res += seg.sum(a_pos + 1, n);
        seg.add(a_pos, 1);
        g_offset[index]++;
    }
    return res;
}
#line 10 "dp/test/inversion_number.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto&& e : a) std::cin >> e;
    long long ans1 = inversion_number<int>(a);
    // a -> b への単射 f を作成
    std::map<int, long long> f;
    std::set<long long> seen;
    for (int i = 0; i < n; i++) {
        if (f.count(a[i]) > 0) continue;
        while (true) {
            auto val = rng_auto.rand_int();
            if (seen.count(val) == 0) {
                f[a[i]] = val;
                seen.insert(val);
                break;
            }
        }
    }
    // a -> a_sorted の転倒数 (ans1) と
    // f(a) -> f(a_sorted) の転倒数 (ans2) が一致することを確認
    auto a_sorted = a;
    std::sort(a_sorted.begin(), a_sorted.end());
    std::vector<long long> b(n), b_sorted(n);
    for (int i = 0; i < n; i++) {
        b[i] = f[a[i]];
        b_sorted[i] = f[a_sorted[i]];
    }
    long long ans2 = inversion_number<long long>(b, b_sorted);
    assert(ans1 == ans2);
    std::cout << ans1 << '\n';
    return 0;
}
Back to top page