[Codeforces] Codeforces Round #672 (Div. 2) A. Cubes Sorting

2020年9月25日2020年12月12日

問題

方針

バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。

コード

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

template <class T> struct fenwick_tree {
    //using U = internal::to_unsigned_t<T>;
    using U = T;
public:
    fenwick_tree() : _n(0) {}
    fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

int a[50000];

void solve(ll n) {
    int b[n];
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) {
        p[i] = make_pair(a[i], i);
    }
    sort(p.begin(), p.end());
    for (int i = 0; i < n; i++) {
        b[p[i].second] = i;
    }
    fenwick_tree<ll> ft(n);
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += i - ft.sum(0, b[i]);
        ft.add(b[i], 1);
    }
    if (cnt > (n * (n - 1)) / 2 - 1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        solve(n);
    }
    return 0;
}

参考