[Codeforces] Codeforces Round #672 (Div. 2) A. Cubes Sorting
問題
方針
バブルソートを行った回数を求めるために、フェニック木 (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; }
ディスカッション
コメント一覧
まだ、コメントがありません