NC222497. [USACOOpen2020G]Haircut
描述
输入描述
The first line contains N.
The second line contains A1,A2,…,AN.
输出描述
For each of j=0,1,…,N−1, output the badness of FJ's hair on a new line.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
示例1
输入:
5 5 2 3 3 0
输出:
0 4 4 5 7
说明:
The fourth line of output describes the number of inversions when FJ's hairs are decreased to length 3. Then A=[3,2,3,3,0]A=[3,2,3,3,0] has five inversions: A1>A2,A1>A5,A2>A5,A3>A5,A1>A2,A1>A5,A2>A5,A3>A5, and A4>A5C++ 解法, 执行用时: 584ms, 内存消耗: 11296K, 提交时间: 2022-03-29 10:49:47
// USACO 2020 Open G. Haircut
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
vector<vector<int>> Loc(N + 1);
for (int i = 0, a; i < N; ++i) cin >> a, Loc[a].push_back(i);
Tree<int> T;
vector<long long> cInv(N + 2);
for (int a = N; a >= 0; --a) {
for (int t : Loc[a]) cInv[a + 1] += T.order_of_key(t);
for (int t : Loc[a]) T.insert(t);
}
_for(i, 1, N) cInv[i] += cInv[i - 1];
_for(i, 0, N) cout << cInv[i] << endl;
}
// Accepted 100 [USACO20OPEN]Haircut G 964ms 10.06MB 740B C++11