For each $0\le j<N$ we need to count the number of pairs $(x,y)$ such that $x<y$, $A[x]>A[y]$ and $A[y]<j$. It suffices to compute the number of $x<y$ such that $A[x]>A[y]$ for every $y$; call this quantity $n[y]$. Then $ans[j]=\sum_{A[y]<j}n[y]$ can be computed with prefix sums.
The value of $n[y]$ for each $y$ can be found via the following process:
The collection can be a policy-based data structure in C++ or a binary indexed tree.
My code:
#include "bits/stdc++.h" using namespace std; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } #include <ext/pb_ds/tree_policy.hpp> #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>; const int MX = 1e5+5; int N; long long numInv[MX]; vector<int> todo[MX]; int main() { setIO("haircut"); int N; cin >> N; vector<int> A(N); for (int& t: A) cin >> t; for (int i = 0; i < N; ++i) todo[A[i]].push_back(i); Tree<int> T; for (int i = N; i >= 0; --i) { for (int t: todo[i]) numInv[i+1] += T.order_of_key(t); for (int t: todo[i]) T.insert(t); } for (int i = 1; i < N; ++i) numInv[i] += numInv[i-1]; for (int i = 0; i < N; ++i) cout << numInv[i] << "\n"; }
Dhruv Rohatgi's code:
#include <iostream> #include <algorithm> using namespace std; #define MAXN 100005 int N; int A[100000]; int T[MAXN+1]; int getSum(int i) { int c=0; for(++i; i > 0 ; i -= (i & -i)) c += T[i]; return c; } void set(int i,int dif) { for(++i; i < MAXN ; i += (i & -i)) T[i] += dif; } long long cnt[100000]; int main() { freopen("haircut.in","r",stdin); freopen("haircut.out","w",stdout); cin >> N; int a; for(int i=0;i<N;i++) { cin >> a; a++; cnt[a] += i - getSum(a); set(a, 1); } long long ans = 0; for(int j=1;j<=N;j++) { cout << ans << '\n'; ans += cnt[j]; } }