cpp_src/utility/Helper.hpp

• View this file on GitHub
• Last update: 2022-08-15 00:57:39+09:00
• Include: #include "cpp_src/utility/Helper.hpp"

Code

template <class T>
void make_unique(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

template <class T>
T pow(T x, ll k) {
    T res(1);
    while (k) {
        if (k & 1) {
            res = res * x;
        }
        k >>= 1;
        x = x * x;
    }
    return res;
}

// x^k mod m
template <class T>
T powmod(T x, ll k, T m) {
    T res(1);
    while (k) {
        if (k & 1) {
            res = res * x % m;
        }
        k >>= 1;
        x = x * x % m;
    }
    return res;
}

template <class T>
V<int> compress(const V<T>& vec) {
    int n = SZ(vec);
    auto xs = vec;
    mkuni(xs);
    V<int> res(n);
    rep(i, n) { res[i] = lower_bound(ALL(xs), vec[i]) - xs.begin(); }
    return res;
}

// 0 <= vec[i] < n
template <class T>
ll inversion(const V<T>& vec) {
    int n = vec.size();
    BIT<int> bit(n + 10);
    ll res = 0;
    rep(i, n) {
        res += i - bit.sum(vec[i] + 1);
        bit.add(vec[i], 1);
    }
    return res;
}

#line 1 "cpp_src/utility/Helper.hpp"
template <class T>
void make_unique(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

template <class T>
T pow(T x, ll k) {
    T res(1);
    while (k) {
        if (k & 1) {
            res = res * x;
        }
        k >>= 1;
        x = x * x;
    }
    return res;
}

// x^k mod m
template <class T>
T powmod(T x, ll k, T m) {
    T res(1);
    while (k) {
        if (k & 1) {
            res = res * x % m;
        }
        k >>= 1;
        x = x * x % m;
    }
    return res;
}

template <class T>
V<int> compress(const V<T>& vec) {
    int n = SZ(vec);
    auto xs = vec;
    mkuni(xs);
    V<int> res(n);
    rep(i, n) { res[i] = lower_bound(ALL(xs), vec[i]) - xs.begin(); }
    return res;
}

// 0 <= vec[i] < n
template <class T>
ll inversion(const V<T>& vec) {
    int n = vec.size();
    BIT<int> bit(n + 10);
    ll res = 0;
    rep(i, n) {
        res += i - bit.sum(vec[i] + 1);
        bit.add(vec[i], 1);
    }
    return res;
}

Back to top page