結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー QDSN
提出日時 2020-07-17 22:34:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 2,371 bytes
コンパイル時間 2,176 ms
コンパイル使用メモリ 182,728 KB
実行使用メモリ 11,188 KB
最終ジャッジ日時 2024-11-30 01:26:02
合計ジャッジ時間 6,289 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
template <typename Mnd> struct segment_tree {
    int sz;
    vector<Mnd> data;
    function<Mnd(Mnd, Mnd)> f;
    Mnd e;
    //サイズだけ指定して初期化
    segment_tree(int _sz, function<Mnd(Mnd, Mnd)> _f, Mnd _e) : f(_f), e(_e) {
        sz = 1;
        while(sz < _sz)
            sz <<= 1;
        data.assign(sz * 2, e);
    }
    //参照渡しなので代入とかもできる
    Mnd &operator[](const int &k) { return data[k + sz]; }
    //木を構築 O(n)
    void build() {
        for(int i = sz - 1; i > 0; i--)
            data[i] = f(data[2 * i], data[2 * i + 1]);
    }
    //更新しつつ木を再構築 O(log n)
    void update(int k, Mnd x) {
        data[k += sz] = x;
        while(k >>= 1)
            data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    //[a,b)でのクエリに答える　O(log n)
    Mnd query(int a, int b) const {
        Mnd l = e, r = e;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if(a & 1)
                l = f(l, data[a++]);
            if(b & 1)
                r = f(r, data[--b]);
        }
        return f(l, r);
    }
};
// 各項の順序を保ったまま最小値0,最大値size()-1以下にする
template <typename T> vector<T> simplify(vector<T> &a) {
    int n = a.size();
    vector<T> b = a;
    sort(b.begin(), b.end());
    vector<T> res(n);
    for(int i = 0; i < n; i++)
        res[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    return res;
}
// 転倒数を計算
// depend:segment_tree
template <typename T> long long inversion_number(vector<T> &a) {
    using lint = long long int;
    int n = a.size();
    vector<T> b = simplify(a);
    segment_tree<lint> count(
        n, [](lint a, lint b) { return a + b; }, 0);
    lint res = 0;
    for(int i = 0; i < n; i++) {
        res += count.query(b[i] + 1, n);
        count.update(b[i], count[b[i]] + 1);
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        mp[b[i]] = i;
    }
    for(int i = 0; i < n; i++) {
        a[i] = mp[a[i]];
    }
    cout << inversion_number(a) << endl;
}
0