You are given a permutation $p_1, p_2, \ldots, p_n$.
In one move you can swap two adjacent values.
You want to perform a minimum number of moves, such that in the end there will exist a subsegment $1,2,\ldots, k$, in other words in the end there should be an integer $i$, $1 \leq i \leq n-k+1$ such that $p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$.
Let $f(k)$ be the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation.
You need to find $f(1), f(2), \ldots, f(n)$.Input
The first line of input contains one integer $n$ ($1 \leq n \leq 200\,000$): the number of elements in the permutation.
The next line of input contains $n$ integers $p_1, p_2, \ldots, p_n$: given permutation ($1 \leq p_i \leq n$).Output
Print $n$ integers, the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation, for $k=1, 2, \ldots, n$.Examplesinput
5 5 4 3 2 1
output
0 1 3 6 10
input
3 1 2 3
output
0 0 0
Solution:
#include <bits/stdc++.h> using namespace std; template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; class segtree { public: struct node { // don't forget to set default value (used for leaves) // not necessarily neutral element! long long L = 0; long long R = 0; int alive = 1; int addL = 0; int addR = 0; void apply(int l, int r) { alive = 0; L = R = 0; addL = addR = 0; } void apply(int l, int r, int v, char c) { if (c == 'L') { L += (long long) alive * v; addL += v; } if (c == 'R') { R += (long long) alive * v; addR += v; } } }; node unite(const node &a, const node &b) const { node res; res.L = a.L + b.L; res.R = a.R + b.R; res.alive = a.alive + b.alive; return res; } inline void push(int x, int l, int r) { int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); if (tree[x].addL != 0) { tree[x + 1].apply(l, y, tree[x].addL, 'L'); tree[z].apply(y + 1, r, tree[x].addL, 'L'); tree[x].addL = 0; } if (tree[x].addR != 0) { tree[x + 1].apply(l, y, tree[x].addR, 'R'); tree[z].apply(y + 1, r, tree[x].addR, 'R'); tree[x].addR = 0; } } inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); } int n; vector<node> tree; void build(int x, int l, int r) { if (l == r) { return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); build(x + 1, l, y); build(z, y + 1, r); pull(x, z); } template <typename M> void build(int x, int l, int r, const vector<M> &v) { if (l == r) { tree[x].apply(l, r, v[l]); return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); build(x + 1, l, y, v); build(z, y + 1, r, v); pull(x, z); } node get(int x, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return tree[x]; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); push(x, l, r); node res{}; if (rr <= y) { res = get(x + 1, l, y, ll, rr); } else { if (ll > y) { res = get(z, y + 1, r, ll, rr); } else { res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr)); } } pull(x, z); return res; } template <typename... M> void modify(int x, int l, int r, int ll, int rr, const M&... v) { if (ll <= l && r <= rr) { tree[x].apply(l, r, v...); return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); push(x, l, r); if (ll <= y) { modify(x + 1, l, y, ll, rr, v...); } if (rr > y) { modify(z, y + 1, r, ll, rr, v...); } pull(x, z); } int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) { if (l == r) { return l; } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res; if (f(tree[x + 1])) { res = find_first_knowingly(x + 1, l, y, f); } else { res = find_first_knowingly(z, y + 1, r, f); } pull(x, z); return res; } int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) { if (ll <= l && r <= rr) { if (!f(tree[x])) { return -1; } return find_first_knowingly(x, l, r, f); } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res = -1; if (ll <= y) { res = find_first(x + 1, l, y, ll, rr, f); } if (rr > y && res == -1) { res = find_first(z, y + 1, r, ll, rr, f); } pull(x, z); return res; } int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) { if (l == r) { return l; } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res; if (f(tree[z])) { res = find_last_knowingly(z, y + 1, r, f); } else { res = find_last_knowingly(x + 1, l, y, f); } pull(x, z); return res; } int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) { if (ll <= l && r <= rr) { if (!f(tree[x])) { return -1; } return find_last_knowingly(x, l, r, f); } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res = -1; if (rr > y) { res = find_last(z, y + 1, r, ll, rr, f); } if (ll <= y && res == -1) { res = find_last(x + 1, l, y, ll, rr, f); } pull(x, z); return res; } segtree(int _n) : n(_n) { assert(n > 0); tree.resize(2 * n - 1); build(0, 0, n - 1); } template <typename M> segtree(const vector<M> &v) { n = v.size(); assert(n > 0); tree.resize(2 * n - 1); build(0, 0, n - 1, v); } node get(int ll, int rr) { assert(0 <= ll && ll <= rr && rr <= n - 1); return get(0, 0, n - 1, ll, rr); } node get(int p) { assert(0 <= p && p <= n - 1); return get(0, 0, n - 1, p, p); } template <typename... M> void modify(int ll, int rr, const M&... v) { assert(0 <= ll && ll <= rr && rr <= n - 1); modify(0, 0, n - 1, ll, rr, v...); } // find_first and find_last call all FALSE elements // to the left (right) of the sought position exactly once int find_first(int ll, int rr, const function<bool(const node&)> &f) { assert(0 <= ll && ll <= rr && rr <= n - 1); return find_first(0, 0, n - 1, ll, rr, f); } int find_last(int ll, int rr, const function<bool(const node&)> &f) { assert(0 <= ll && ll <= rr && rr <= n - 1); return find_last(0, 0, n - 1, ll, rr, f); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; --p[i]; } vector<int> pos(n); for (int i = 0; i < n; i++) { pos[p[i]] = i; } fenwick<int> fenw(n); vector<long long> res(n); long long inv = 0; segtree st(n); for (int it = 0; it < n; it++) { int at = pos[it]; inv += fenw.get(n - 1) - fenw.get(at); fenw.modify(at, +1); if (at > 0) { st.modify(0, at - 1, 1, 'R'); } if (at < n - 1) { st.modify(at + 1, n - 1, 1, 'L'); } st.modify(at, at); int med = -1; { int low = 0, high = n - 1; while (low < high) { int mid = (low + high) >> 1; int s = fenw.get(mid); if (s >= it / 2 + 1) { high = mid; } else { low = mid + 1; } } med = low; } res[it] = inv; if (med > 0) { res[it] += st.get(0, med - 1).L; } if (med < n - 1) { res[it] += st.get(med + 1, n - 1).R; } } for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << res[i]; } cout << '\n'; return 0; }