Codeforces Round #609 - C. K Integers

https://codeforces.com/contest/1268/problem/C

Problem - C - Codeforces

역시 문제 기술 짧고 간단하다.

 

퍼뮤테이션  배열 $p_1, p_2, \dots, p_n$이 들어온다.($1 \leq n \leq 2\cdot 10^5$)

배열의 인접한 두 원소의 값을 바꾸는 동작을 실행할 수 있다.

어떤 $k$에 대해 $p_i = 1$, $p_{i+1} = 2$, ..., $p_{i+k-1} = k$를 만족하도록 시행해야할 동작의 최소 횟수를 $f(k)$라고 하자.

$f(1), f(2), \dots, f(n)$을 공백을 간격으로 출력하여라.

 

 

(풀이)

 

본격 라이브러리빨 문제

 

퍼뮤테이션의 위치 배열을 $pos$라고 하자. (즉, $pos = p^{-1}$)

 

$f(k)$를 구하는 단계에서 $pos[1], pos[2], \dots, pos[k]$ 원소를 결과적으로 $s+1, s+2, \dots, s+k$ 번째 원소로 만드려고할 때 최소 비용을 생각해보자. 이는 두 요소의 합이다.

1. $pos[1], pos[2], \dots, pos[k]$ 서로 간에 swap 없이 위치만 $s+1, s+2, \dots, s+k$ 번째로 만드는 동작
   • 즉, $pos[1] = 6, pos[2] = 4, pos[3] = 2$, $s = 2$이라면 배열 내 원소가 { . . 3 2 1 . .} 가 되게 만드는데 필요한 동작
2. 위치가 수정된 상태에서 퍼뮤테이션 위치를 재배열하는 동작
   
   • 즉, 위 예시에서 { . . 1 2 3 . . } 으로 수정하는데 필요한 동작

 

2번 동작에서 필요한 최소 횟수는 inversion의 개수를 세기만 하면 된다. lower bound는 자명하고, upper bound는 수학적 귀납법으로 쉽게 증명이 된다.

 

문제는 1번 동작에 필요한 최소 횟수를 구하는 것이다. 적절한 $s$ 값을 설정하기도, 필요한 횟수를 구하기도 굉장히 까다롭다.

 

$pos[1], pos[2], \dots, pos[k]$ 를 정렬하여 오름차순으로 $q[1], q[2], \dots, q[k]$라고 하자. 1번 동작에 필요한 최소 비용은

$$ \sum_{i=1}^k \left| s + i - q[i] \right| = \sum_{i=1}^k \left| s - (q[i] - i) \right| $$

이다. 1차 항의 계수가 1인 절대값 함수의 합이고, 이 볼록함수의 최소점은 $s$가 $q[i] - i$ 값들 중 중간값 위치일 때 성립한다.

 

조금 더 생각해보면 $q[i] < q[i+1]$ 이므로(퍼뮤테이션 위치니까), $q[i] - i \leq q[i+1] - (i+1)$ 을 만족한다. 그러므로 $q[i]$ 값들 중 중간값에 해당하는 원소에 대해서 처리해주면 $q[i] - i$ 값들 중 중간값에 대해서 처리가 되는거랑 마찬가지다.

 

그 중간값이 $q[m]$ 라고 하자. (즉, $m$번째 원소) 그렇다면 구해야하는 1번 동작 최소 횟수 값은

$$ \sum_{i=1}^m (s + i - q[i]) + \sum_{i=m+1}^k (q[i] - s - i) $$

이다. 나는 treap_sum 라이브러리에 $1 \sim k$ 번째 원소들의 합과, 큰 값 순서대로 $1 \sim k$ 번째 원소들의 합을 $O(\log n)$ 만에 구하는 코드를 이미 구현해놨다.

 

그걸로 빠르게 풀었다. ㅎㅎ (물론 long long 대신 int 써서 뚝배기 깨지긴 했다.)

 

Virtual Round 아니었음 오렌지 갔을 것 같은데 아깝다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;/*{{{*/
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> piii;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> plll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pil> vil;
typedef vector<pll> vll;
typedef vector<piii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef int (*itoi) (int);
typedef int (*iitoi) (int, int);
typedef int (*iiitoi) (int, int, int);
typedef ll (*ltol) (ll);
typedef ll (*lltol) (ll, ll);
typedef ll (*llltol) (ll, ll, ll);

const ld PI = acos(0)*2;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll*INF*INF;
int X4[] = {-1, 0, 1, 0}, Y4[] = {0, -1, 0, 1};
int X8[] = {-1, -1, -1, 0, 1, 1, 1, 0}, Y8[] = {-1, 0, 1, 1, 1, 0, -1, -1};

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) ((int) (x).size())
#define NTH(v, x) ((int) (lower_bound(ALL(v), (x)) - (v).begin()))
#define SAME(v, x) ((int) (upper_bound(ALL(v), (x)) - lower_bound(ALL(v), (x))))
#define UNIQUE(v) v.erase(unique(ALL(v)), (v).end())
#define WER << ' ' <<

#define pb push_back
#define eb emplace_back
#define INP(t, x) t x; cin >> x

#define CPPIO ios::sync_with_stdio(0); cin.tie(0); cout << std::setprecision(10); cout << fixed

#define forn(x, n) for (int x=0; x<(n); x++)
#define for1(x, n) for (int x=1; x<=(n); x++)
#define ford(x, n) for (int x=(n)-1; x>=0; x--)
#define ford1(x, n) for (int x=(n); x>=1; x--)
#define forr(x, n, m) for (int x=(n); x<=(m); x++)
#define forrd(x, n, m) for (int x=(m); x>=(n); x--)

template<typename T> inline bool uax(T &a, T b) { return a<b? (a=b, 1) : 0; }
template<typename T> inline bool uin(T &a, T b) { return a>b? (a=b, 1) : 0; }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& p) {
	return is >> p.first >> p.second;
}
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& p) {
	return os << '(' << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i=0; i<(int)v.size(); i++) { os << v[i]; if (i+1<(int)v.size()) os << ' '; } return os;
}/*}}}*/

// library 'binary_indexed_tree.cpp'{{{
//
//////// ---- Woosung Song's Source Code ---- ////////

// binary indexed tree with operators.

#ifndef BINARY_INDEXED_TREE_DEFINED
template <class sum_type>
class binary_indexed_tree {
	private:
		typedef sum_type (*sum_op) (sum_type, sum_type);
		sum_op DEFAULT_ADD_OP = [](sum_type a, sum_type b) { return a + b; };
		sum_type DEFAULT_ADD_ID = 0;
	
	public:
		int max_index, min_index;
		int size;
		vector<sum_type> v;

		sum_op add_op = DEFAULT_ADD_OP;
		sum_type add_id = DEFAULT_ADD_ID;

		binary_indexed_tree<sum_type>() {}

		binary_indexed_tree<sum_type>(int min_index, int max_index,
				sum_op add_op=0, sum_type add_id=0) {
			this->max_index = max_index, this->min_index = min_index;
			if (add_op) this->add_op = add_op, this->add_id = add_id;
			assert(min_index <= max_index);
			for (size=1; size<max_index-min_index+1; size<<=1);
			v.assign(size * 2, add_id);
		}

		void update(int p, sum_type x) {
			assert(min_index <= p && p <= max_index);
			v[p=p-min_index+size] = x;
			for (p>>=1; p; p>>=1) {
				v[p] = add_op(v[p+p], v[p+p+1]);
			}
		}

		sum_type sum(int l, int r) {
			assert(min_index <= l && l <= r && r <= max_index);
			sum_type s = add_id;
			l = l - min_index + size, r = r - min_index + size;
			for (; l<=r; l>>=1, r>>=1) {
				if (l & 1) s = add_op(s, v[l++]);
				if ((r+1)&1) s = add_op(s, v[r--]);
			}
			return s;
		}
};
#endif

#define BINARY_INDEXED_TREE_DEFINED

//////// ---- Woosung Song's Source Code ---- ////////}}}

// library 'treap_sum.cpp'{{{
//
//////// ---- Woosung Song's Source Code ---- ////////

// an efficient data structure that implements binary tree
// supports kth, count_greator, sum_greater ..., and e.t.c.
// `sum' operator is enabled

#ifndef TREAP_SUM_DEFINED
template <class element_type, class sum_type>
class __treap_sum_node {/*{{{*/
	public:
		element_type key;
		sum_type sum;
		int priority, num_nodes, count;
		__treap_sum_node *left, *right;

		__treap_sum_node(element_type k, int cnt=1) : key(k), sum(cnt * ((sum_type) k)), priority(rand()), num_nodes(cnt), count(cnt), left(0), right(0) {}
		void calc_num_node() { num_nodes = count + (left? left->num_nodes : 0) + (right? right->num_nodes : 0); }
		void calc_sum() { sum = count * key + (left? left->sum : 0) + (right? right->sum : 0); }
		void set_left(__treap_sum_node *t) { left = t; calc_num_node(); calc_sum(); }
		void set_right(__treap_sum_node *t) { right = t; calc_num_node(); calc_sum(); }
};/*}}}*/

template <class element_type, class sum_type>
using __treap_sum_pair = pair<__treap_sum_node<element_type, sum_type>*, __treap_sum_node<element_type, sum_type>* >;

template <class element_type, class sum_type>
struct treap_sum {
	private:
		typedef __treap_sum_node<element_type, sum_type> node;/*{{{*/
		typedef __treap_sum_pair<element_type, sum_type> node_pair;

		node *root;
		int num_nodes;/*}}}*/

	public:
		sum_type sum;
		bool enable_duplicates;
		treap_sum(bool _enable_duplicates=1) : root(0), num_nodes(0), sum(0), enable_duplicates(_enable_duplicates) {}

	private:
		node_pair* __splited(node *r, element_type key) {/*{{{*/
			if (!r) return new node_pair(0, 0);
			if (r->key < key) {
				node_pair *p = __splited(r->right, key);
				r->set_right(p->first);
				return new node_pair(r, p->second);
			} else {
				node_pair *p = __splited(r->left, key);
				r->set_left(p->second);
				return new node_pair(p->first, r);
			}
		}

		node* __find_node(node *r, element_type key, int inc=0) {
			if (!r) return 0;
			if (r->key == key) {
				if (inc) r->count += inc, r->calc_num_node(), r->calc_sum();
				return r;
			}
			if (r->key < key) {
				if (inc) r->num_nodes += inc, r->sum += inc * key;
				return __find_node(r->right, key, inc);
			}
			if (inc) r->num_nodes += inc, r->sum += inc * key;
			return __find_node(r->left, key, inc);
		}

		node* __insert_node(node *r, node *n) {
			if (!r) return n;
			if (r->priority < n->priority) {
				node_pair *p = __splited(r, n->key);
				n->set_left(p->first);
				n->set_right(p->second);
				return n;
			}
			if (n->key < r->key) r->set_left(__insert_node(r->left, n));
			else r->set_right(__insert_node(r->right, n));
			return r;
		}

		node* __merge_node(node *n1, node *n2) {
			if (!n1) return n2;
			else if (!n2) return n1;
			else if (n1->priority < n2->priority) {
				n2->set_left(__merge_node(n1, n2->left));
				return n2;
			} else {
				n1->set_right(__merge_node(n1->right, n2));
				return n1;
			}
		}

		node* __erase_node(node *n, element_type key) {
			if (!n) return n;
			if (n->key == key) {
				node* ret = __merge_node(n->left, n->right);
				delete n;
				return ret;
			}
			if (key < n->key) n->set_left(__erase_node(n->left, key));
			else n->set_right(__erase_node(n->right, key));
			return n;
		}

		node* __kth_node(node* n, int k) {
			int left = 0;
			if (n->left) left = n->left->num_nodes;
			if (k <= left) return __kth_node(n->left, k);
			if (left+1 <= k && k <= left+n->count) return n;
			return __kth_node(n->right, k-left-n->count);
		}

		element_type __kth_smallest_sum(node* n, int k) {
			int left = 0;
			element_type left_sum = 0;
			if (n->left) left = n->left->num_nodes, left_sum = n->left->sum;
			if (k <= left) return __kth_smallest_sum(n->left, k);
			if (left+1 <= k && k <= left+n->count) return (k-left)*(n->key) + left_sum;
			return left_sum + (n->count)*(n->key) + __kth_smallest_sum(n->right, k-left-n->count);
		}

		int __count_greater(node* n, element_type key) {
			if (!n) return 0;
			if (n->key <= key) return __count_greater(n->right, key);
			return n->count + (n->right? n->right->num_nodes : 0) + __count_greater(n->left, key);
		}

		int __count_less(node* n, element_type key) {
			if (!n) return 0;
			if (n->key >= key) return __count_less(n->left, key);
			return n->count + (n->left? n->left->num_nodes : 0) + __count_less(n->right, key);
		}

		element_type __sum_greater(node* n, element_type key) {
			if (!n) return 0;
			if (n->key <= key) return __sum_greater(n->right, key);
			return (n->right? n->right->sum : 0) + (n->count * n->key) + __sum_greater(n->left, key);
		}

		element_type __sum_less(node* n, element_type key) {
			if (!n) return 0;
			if (n->key >= key) return __sum_less(n->left, key);
			return (n->left? n->left->sum : 0) + (n->count * n->key) + __sum_less(n->right, key);
		}

		void __print_node(node *n) {
			if (n) {
				__print_node(n->left);
				//cout << (n->key) << '(' << (n->count) << ')' << ' ';
				for (int i=0; i<n->count; i++) cout << n->key << ' ';
				__print_node(n->right);
			}
		}

		node* __biggest(node *n) {
			if (n->right) return __biggest(n->right);
			else return n;
		}

		node* __smallest(node *n) {
			if (n->left) return __smallest(n->left);
			else return n;
		}

		void __disable_duplicates(node *n) {
			n->count = 1;
			if (n->left) __disable_duplicates(n->left);
			if (n->right) __disable_duplicates(n->right);
			n->calc_num_node();
			n->calc_sum();
		}

		void __vectorize(node *n, vector<element_type> &v) {
			if (n->left) __vectorize(n->left, v);
			for (int i=0; i<n->count; i++) v.push_back(n->key);
			if (n->right) __vectorize(n->right, v);
		}/*}}}*/
	
	public:
		int size() {/*{{{*/
			return num_nodes;
		}/*}}}*/

		bool empty() {/*{{{*/
			return num_nodes == 0;
		}/*}}}*/

		void print() {/*{{{*/
			// print the treap_sum tree in sorted order
			__print_node(root);
			cout << "(num_nodes: " << num_nodes << ", sum: " << sum << ")" << endl;
		}/*}}}*/

		void insert(element_type key, int cnt=1) {/*{{{*/
			// insert an element of the given key
			node *f = __find_node(root, key);
			if (!enable_duplicates) cnt = 1;
			if (f) {
				__find_node(root, key, enable_duplicates? cnt : 0);
			} else {
				node *n = new node(key, cnt);
				root = __insert_node(root, n);
			}
			num_nodes = root->num_nodes;
			sum = root->sum;
		}/*}}}*/

		bool erase(element_type key, int cnt=1) {/*{{{*/
			// erase an element with the given key
			// returns 1 iff tree has a node of the key
			node *f = __find_node(root, key);
			if (f) {
				if (f->count <= cnt) root = __erase_node(root, key);
				else __find_node(root, key, -cnt);
				num_nodes = root? root->num_nodes : 0;
				sum = root? root->sum : 0;
				return 1;
			} else return 0;
		}/*}}}*/

		bool erase_key(element_type key) {/*{{{*/
			// erase a tree node with the given key (for every count)
			// returns 1 iff tree has a node of the key
			node *f = __find_node(root, key);
			if (f) {
				root = __erase_node(root, key);
				num_nodes = root? root->num_nodes : 0;
				sum = root? root->sum : 0;
				return 1;
			} else return 0;
		}/*}}}*/

		element_type kth(int k) {/*{{{*/
			// the kth smallest element
			assert(1 <= k && k <= num_nodes);
			return __kth_node(root, k)->key;
		}/*}}}*/

		element_type kth_biggest(int k) {/*{{{*/
			return kth(num_nodes + 1 - k);
		}/*}}}*/

		element_type kth_smallest_sum(int k) {/*{{{*/
			// the sum of 1st to kth smallest elements
			assert(1 <= k && k <= num_nodes);
			return __kth_smallest_sum(root, k);
		}/*}}}*/

		element_type kth_biggest_sum(int k) {/*{{{*/
			// the sum of 1st to kth biggest elements;
			assert(1 <= k && k <= num_nodes);
			return sum - __kth_smallest_sum(root, num_nodes-k);
		}/*}}}*/

		int count(element_type key) {/*{{{*/
			// count the duplicates of the key
			node *f = __find_node(root, key);
			return f? f->count : 0;
		}/*}}}*/

		int count_greater(element_type key) {/*{{{*/
			// count the number of elements whose key is greater than key
			return __count_greater(root, key);
		}/*}}}*/

		int count_less(element_type key) {/*{{{*/
			// count the number of elements whose key is less than key
			return __count_less(root, key);
		}/*}}}*/

		element_type sum_same(element_type key) {/*{{{*/
			// sum of the elements whose keys are same to the given key
			node *f = __find_node(root, key);
			return f? (f->count * f->key) : 0;
		}/*}}}*/

		element_type sum_greater(element_type key) {/*{{{*/
			// sum of the elements whose keys are greater than the given key
			return __sum_greater(root, key);
		}/*}}}*/

		element_type sum_less(element_type key) {/*{{{*/
			// sum of the elements whose keys are less than the given key
			return __sum_less(root, key);
		}/*}}}*/

		element_type biggest() {/*{{{*/
			// find the biggest key
			assert(root);
			return __biggest(root)->key;
		}/*}}}*/

		element_type smallest() {/*{{{*/
			// find the smallest key
			assert(root);
			return __smallest(root)->key;
		}/*}}}*/

		void set_duplicates(bool duplicates) {/*{{{*/
			// allow duplicates or not
			if (enable_duplicates == duplicates) return;
			enable_duplicates = duplicates;
			if (!duplicates) {
				if (root) __disable_duplicates(root);
				num_nodes = root? root->num_nodes : 0;
				sum = root? root->sum : 0;
			}
		}/*}}}*/

	vector<element_type>& vectorize() {/*{{{*/
		vector<element_type> *pv = new vector<element_type>(), &v = *pv;
		if (root) __vectorize(root, v);
		return v;
	}/*}}}*/
};
#endif

#define TREAP_SUM_DEFINED

//////// ---- Woosung Song's Source Code ---- ////////}}}

//////// ---- Woosung Song's Source Code ---- ////////


const int MAX_N = 2e5 + 20;

int N;
int P[MAX_N], Pos[MAX_N];
binary_indexed_tree<int> Bit(1, MAX_N);
treap_sum<ll,ll> Tr;


int main() {
	CPPIO;
	
	//////// ---- Woosung Song's Source Code ---- ////////
	
	cin >> N;
	for1(i, N) {
		cin >> P[i];
		Pos[P[i]] = i;
	}

	ll cntinv = 0;

	for (ll k=1; k<=N; k++) {
		cntinv += Bit.sum(Pos[k], N);
		Bit.update(Pos[k], 1);

		Tr.insert(Pos[k]);
		ll mid = (k+1)/2, rem = k - mid;
		ll q_m = Tr.kth(mid);
		ll s = q_m - mid;

		ll sum = s * mid + mid * (mid+1) / 2 - s * rem - (k*(k+1)/2 - mid*(mid+1)/2);
		sum -= Tr.kth_smallest_sum(mid);
		sum += rem>0? Tr.kth_biggest_sum(rem) : 0;

		cout << sum+cntinv << ' ';
	}
	cout << endl;
	
	
#ifdef LOCAL_DEFINE/*{{{*/
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif
	return 0;/*}}}*/
}