重要なお知らせ

このデータ構造のソースコードに致命的なバグがあることが判明しました。

このサイト内のセグメント木で代用するかAtcoder公式ライブラリなどの信頼できるライブラリを使用してください...申し訳ないです 

    
/*
BIT<long long> data(n);などで宣言(初期値は0)
または配列の値をvector<long long> a(n)などで初期化したいとき
BIT<long long> data(n,a);で宣言
以下0-indexedと仮定する
data.sum(l,r):区間[l,r]の和
data.at(i):i番目の値
data.add(i,x):i番目にxを加算 
*/
template <typename T>
struct BIT
{
private:
    vector<T> bit;
    int n;
    T sum(int x)
    {
        T ret = 0;
        while (x > 0)
        {
            ret += bit[x];
            x -= x & -x;
        }
        return ret;
    }

public:
    BIT(int n0) : bit(n0 + 1, 0), n(n0) {}
    BIT(int n0, vector<T> &A) : bit(n0 + 1, 0), n(n0)
    {
        for (int i = 1; i <= n; i++)
            bit[i] = A[i - 1];
        for (int i = 1; i < n; i++)
            bit[i + (i & -i)] += bit[i];
    }
    T sum(int l, int r)
    {
        return sum(r + 1) - sum(l);
    }
    T at(int x)
    {
        return sum(x, x);
    }
    void add(int p, T x)
    {
        int i = p + 1;
        while (i <= n)
        {
            bit[i] += x;
            i += i & -i;
        }
    }
};
//配列の数値が小さい順に0-indexedでナンバリングする(同種なら同じ値)
//配列を書き換えるので、必要ならばあらかじめ圧縮前の配列を別に保存しておく
template <typename T>
void press(vector<T> &A)
{
    vector<T> sorted = A;
    sort(sorted.begin(), sorted.end());
    auto itr = unique(sorted.begin(), sorted.end());
    sorted.erase(itr, sorted.end());
    for (int i = 0; i < A.size(); i++)
        A[i] = lower_bound(sorted.begin(), sorted.end(), A[i]) - sorted.begin();
    return;
}
//配列Aの転倒数を求める
template <typename T>
T inversion(vector<T> A)
{
    T siz = A.size();
    //まずは座圧
    vector<T> B = A;
    press(B);
    BIT<T> inv(siz);
    T ret = 0;
    for (int i = 0; i < siz; i++)
    {
        ret += (i - inv.sum(0, B[i]));
        inv.add(B[i], 1);
    }
    return ret;
}
© 2020 kacho65535