結果
問題 |
No.694 square1001 and Permutation 3
|
ユーザー |
|
提出日時 | 2018-09-14 06:05:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,753 ms / 3,000 ms |
コード長 | 2,259 bytes |
コンパイル時間 | 2,451 ms |
コンパイル使用メモリ | 208,636 KB |
最終ジャッジ日時 | 2025-01-06 13:15:56 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h> struct Sum { using T = int; T operator()(const T& a, const T& b) const { return a + b; } static constexpr T id() { return 0; } }; template <typename Base> class BinaryIndexedTree { static constexpr int sz(const int n) { int ans = 1; for (; n > ans; ans <<= 1) { } return ans; } public: using T = typename Base::T; using AbelGroup = Base; BinaryIndexedTree(const int n) : data_num(n), size(sz(n)), value(size + 1, Base::id()) { assert(n > 0); } template <typename InIt> BinaryIndexedTree(const InIt first, const InIt last) : data_num(distance(first, last)), size(sz(data_num)), value(size + 1, Base::id()) { copy(first, last, value.begin() + 1); for (int x = 1; x < size; x++) { value[x + (x & -x)] = op(value[x + (x & -x)], value[x]); } } T accumulate(const int a) const // [0,a] { T sum = Base::id(); for (int ind = a + 1; ind > 0; ind &= ind - 1) { sum = op(sum, value[ind]); } return sum; } void add(const int a, const T& val) { for (int ind = a + 1; ind <= size; ind += ind & (-ind)) { value[ind] = op(value[ind], val); } } private: const int data_num, size; const Base op{}; std::vector<T> value; }; int main() { int N; std::cin >> N; std::vector<int> a(N); for (auto& e : a) { std::cin >> e; } auto b = a; std::sort(b.begin(), b.end()); std::vector<int> l(N), u(N); for (int i = 0; i < N; i++) { l[i] = std::lower_bound(b.begin(), b.end(), a[i]) - b.begin(); u[i] = b.end() - std::upper_bound(b.begin(), b.end(), a[i]); } b.erase(std::unique(b.begin(), b.end()), b.end()); std::map<int, int> mp; for (int i = 0; i < b.size(); i++) { mp[b[i]] = i; } BinaryIndexedTree<Sum> bit(N + 1); long long ans = 0; for (int i = N - 1; i >= 0; i--) { a[i] = mp[a[i]]; ans += bit.accumulate(a[i]); bit.add(a[i] + 1, 1); } std::cout << ans << std::endl; for (int i = 0; i < N - 1; i++) { ans += u[i] - l[i]; std::cout << ans << std::endl; } return 0; }