领奖台数

领奖台数

题意：给定任意一个序列\(a_1,\cdots, a_n\)，其中没有重复元素。如果\(i < j < k\) 且\(a_j > a_i > a_k\)，三个数字的大小关系就像运动会颁奖时的领奖台。于是我们称序列中满足该条件的三元组\((i,j,k)\)的个数为序列的领奖台数。设计一个算法来计算序列的领奖台数。

输入：第一行包含一个正整数\(n\)，表示输入序列的长度。\(n \le 1000000\)

? 第二行输入序列元素\(a_1,...,a_n\)组成，每个元素用空格分隔。\(a_i \in Z, |a_i| \le 10^9\)。

输出：输出同时满足条件的三元组个数

solution：树状数组 + 容斥 + 思维

• 即求"231"三元组个数，\(res\) = \(a_i>a_k\)且\(a_j>a_k\)的个数 \(-\) \(a_i > a_j > a_k\)的个数
• 两个子问题可使用树状数组方便求得，并且题中保证无重复元素，因此无需考虑 \(a_i = a_j > a_k\) 的情况

#include 

using namespace std;
using ll = long long;

struct Fenwick {
    const int n;
    std::vector tr;
    Fenwick(int n) : n(n), tr(n + 1, 0) {}
    void add(int x, int v) {
        for (int i = x; i <= n; i += i & -i) {
            tr[i] += v;
        }
    }
    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= i & -i) {
            res += tr[i];
        }
        return res;
    }
};

int main()
{
    int n; cin >> n;

    std::vectora(n);

    for(int i = 0; i < n; ++i) cin >> a[i];

    Fenwick fen(n);

    auto s = a;
    sort(s.begin(), s.end());
    auto q = [&](int x) {
        return lower_bound(s.begin(), s.end(), x) - s.begin() + 1;
    };

    std::vectorG(n);
    for(int i = 0; i < n; ++i) {
        int x = q(a[i]);
        G[i] = fen.sum(n) - fen.sum(x);
        fen.add(x, 1);
    }

    Fenwick fen1(n);
    std::vectorL(n);
    for(int i = n - 1; i >= 0; --i){
        int x = q(a[i]);
        L[i] = fen1.sum(x - 1);
        fen1.add(x, 1);
    }

    ll res = 0;
    for(int i = 0; i < n; ++i) {
        res += 1ll * G[i] * (G[i] - 1) / 2 - 1ll * L[i] * G[i];
    }
    
    cout << res << endl;

    return 0;
}