結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー 🍮かんプリン
提出日時 2020-10-21 04:36:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,221 ms / 5,000 ms
コード長 3,069 bytes
コンパイル時間 2,334 ms
コンパイル使用メモリ 192,904 KB
実行使用メモリ 85,204 KB
最終ジャッジ日時 2024-07-21 08:46:35
合計ジャッジ時間 10,247 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.10.21 04:36:30
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;



template< typename T >
struct BinaryIndexedTree {
    std::vector< T > data;
    BinaryIndexedTree() {}
    BinaryIndexedTree(int sz) {
        data.assign(++sz, 0);
    }
    
    inline T sum(int k) const {
        T ret = 0;
        for (k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }
    
    inline T sum(int left, int right) const {
        return sum(right) - sum(left);
    }
    
    
    inline void add(int k, T x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
    
    int lower_bound(ll k) const {
        if (k <= 0) return 0;
        int res = 0;
        int N = 1; while (N < (int)data.size()) N *= 2;
        for (int i = N / 2; i > 0; i /= 2) {
            if (res + i < (int)data.size() && data[res + i] < k) {
                k -= data[res + i];
                res += i;
            }
        }
        return res;
    }
    
    friend std::ostream& operator<<(std::ostream &os, const BinaryIndexedTree &bit) {
        os << "[ ";
        for (int i = 0; i < bit.data.size() - 1; i++) {
            os << bit.sum(i, i + 1);
            if (i < bit.data.size() - 2) os << ", ";
        }
        os << " ]";
        return os;
    }
};
int main() {
    int n;cin >> n;
    vector<int> a(n);
    map<int,int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]] = 0;
    }
    int idx = 0;
    for(auto p : mp) {
        mp[p.first] = idx++;
    }
    for (int i = 0; i < n; i++) {
        a[i] = mp[a[i]];
    }
    
    BinaryIndexedTree<int> seg1(n);
    vector<pair<int,int>> b(n);
    for (int i = 0; i < n; i++) {
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b.begin(), b.end());
    vector<int> tmp;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (ll)seg1.sum(b[i].second) * seg1.sum(b[i].second,n);
        if (i == n-1 || b[i].first != b[i+1].first) {
            for (int t : tmp) {
                seg1.add(t,1);
            }
            seg1.add(b[i].second,1);
            tmp.clear();
        }
        else {
            tmp.push_back(b[i].second);
        }
    }
    
    BinaryIndexedTree<int> seg2(n);
    sort(b.rbegin(), b.rend());
    for (int i = 0; i < n; i++) {
        ans += (ll)seg2.sum(b[i].second) * seg2.sum(b[i].second,n);
        if (i == n-1 || b[i].first != b[i+1].first) {
            for (int t : tmp) {
                seg2.add(t,1);
            }
            seg2.add(b[i].second,1);
            tmp.clear();
        }
        else {
            tmp.push_back(b[i].second);
        }
    }
    vector<int> sum(idx);
    for (int i = 0; i < n; i++) {
        sum[a[i]]++;
    }
    vector<int> c(idx);
    BinaryIndexedTree<ll> seg3(idx);
    for (int i = 0; i < n; i++) {
        ans -= seg3.sum(a[i]) + seg3.sum(a[i]+1,idx);
        seg3.add(a[i],sum[a[i]] - 2 * c[a[i]] - 1);
        c[a[i]]++;
    }
    cout << ans << endl;
    return 0;
}
0