/*
 *	31-1-3: Řazení kořenek pomocí Splay stromů
 *
 *	Martin Medvěd Mareš, říjen 2018
 */

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*** Základní datové struktury ***/

#define MAXN 1000

// Vstup
int X[MAXN+1];		// Pozor, prvky číslujeme od 1
			// X[0] je vždy -∞
int n;

// Nejdelší rostoucí posloupnost
int nrp[MAXN];		// Indexy prvků ležících v NRP
int n_nrp;
int in_nrp[MAXN+1];	// in_nrp[x] = 1 <=> x je v NRP

// Výstup: seznam pohybů
int move_x[MAXN];	// Které prvky posouvat
int move_by[MAXN];	// O kolik doprava posouvat
int n_moves;

/*** Rychlý algoritmus na NRP ***/

int P[MAXN+1];	// X[P[i]] = nejmenší možný konec NRP délky i
int B[MAXN+1];	// X[B[i]] = předchůdce prvku X[i]

void find_nrp(void)
{
	X[0] = INT_MIN;
	P[0] = 0;
	int nP = 1;	// Počet hodnot v poli P menších než +∞

	for (int k=1; k<=n; k++) {
		// Binární vyhledávání
		int l = 0, p = nP;
		while (l < p-1) {
			// Invariant: X[P[l]] < X[k] <= X[P[r]]
			int m = (l+p) / 2;
			if (X[P[m]] >= X[k])
				p = m;
			else
				l = m;
		}

		// Přepsání hodnoty na nalezené pozici
		P[p] = k;
		B[k] = P[l];
		if (p >= nP)
			nP++;
	}

	// Rekonstrukce NRP pozpátku
	n_nrp = nP - 1;
	int pos = n_nrp;
	int end = P[pos];
	while (end) {
		in_nrp[X[end]] = 1;
		nrp[--pos] = end;
		end = B[end];
	}
}

/*** Splay stromy ***/

typedef struct node node;

struct node {
	node *l, *r, *p;	// Levý syn, pravý syn, otec
	int x;			// Hodnota prvku
	int w;			// Váha podstromu (počet vrcholů)
};

// Připojí levého syna vrcholu
void s_setl(node *p, node *s)
{
	p->l = s;
	if (s)
		s->p = p;
}

// Připojí pravého syna vrcholu
void s_setr(node *p, node *s)
{
	p->r = s;
	if (s)
		s->p = p;
}

// Vymění ve vrcholu p syna o za n
void s_replace(node *p, node *o, node *n)
{
	if (p) {
		if (p->l == o)
			p->l = n;
		else
			p->r = n;
	}
	n->p = p;
}

// Přepočítá váhu podle synů
void s_recalc(node *x)
{
	x->w = 1 + (x->l ? x->l->w : 0) + (x->r ? x->r->w : 0);
}

// Rotace doleva (x je horní vrchol rotované hrany)
void s_rl(node *x)
{
	node *y = x->r;
	node *b = y->l;
	s_replace(x->p, x, y);
	s_setl(y, x);
	s_setr(x, b);
	s_recalc(x);
	s_recalc(y);
}

// Rotace doprava (x je horní vrchol rotované hrany)
void s_rr(node *x)
{
	node *y = x->l;
	node *b = y->r;
	s_replace(x->p, x, y);
	s_setr(y, x);
	s_setl(x, b);
	s_recalc(x);
	s_recalc(y);
}

// Vysplayuje vrchol x do kořene
void s_splay(node *x)
{
	node *p, *g;

	while ((p = x->p)) {
		bool pl = (x == p->l);
		g = p->p;
		if (g) {
			bool gl = (p == g->l);
			if (gl) {
				if (pl) {
					s_rr(g);
					s_rr(p);
				} else {
					s_rl(p);
					s_rr(g);
				}
			} else {
				if (pl) {
					s_rr(p);
					s_rl(g);
				} else {
					s_rl(g);
					s_rl(p);
				}
			}
		} else {
			if (pl)
				s_rr(p);
			else
				s_rl(p);
		}
	}
}

// Ve vrcholu nodes[x] je uložena hodnota x
node *nodes[MAXN+1];

// Vytvoří strom podle posloupnosti
void s_build(void)
{
	node *prev = NULL;
	for (int i=0; i<=n; i++) {
		node *s = malloc(sizeof(node));
		s->x = i ? X[i] : 0;
		s->p = NULL;
		s_setl(s, prev);
		s->r = NULL;
		s_recalc(s);
		nodes[s->x] = s;
		prev = s;
	}
}

// Spočítá pozici prvku x v posloupnosti
int s_rank(node *x)
{
	s_splay(x);
	return (x->l ? x->l->w : 0);
}

// Odpojí prvek x
void s_remove(node *x)
{
	// nodes[0] will never be removed
	s_splay(x);
	node *l = x->l;
	l->p = NULL;
	node *lmax = l;
	while (lmax->r)
		lmax = lmax->r;
	s_splay(lmax);
	s_setr(lmax, x->r);
	s_recalc(lmax);
	x->l = x->r = NULL;
}

// Zapojí (dříve odpojený) prvek x za prvek after
void s_insert(node *x, node *after)
{
	s_splay(after);
	node *r = after->r;
	s_setr(after, x);
	s_setr(x, r);
	s_recalc(x);
	s_recalc(after);
}

#if 0
// Zobrazování stromu
void s_do_show(node *x, int indent)
{
	if (!x)
		return;
	s_do_show(x->r, indent+1);
	printf("%*s%d [%d]\n", 4*indent, "", x->x, x->w);
	s_do_show(x->l, indent+1);
}

void s_show(void)
{
	node *n = nodes[0];
	while (n->p)
		n = n->p;
	s_do_show(n, 0);
}
#endif

/*** Hledaní pohybů ***/

void find_moves(void)
{
	s_build();
	int next = 1;	// Následující pozice, na kterou chceme přesouvat
	for (int x=1; x<=n; x++) {
		int ix = s_rank(nodes[x]);
		// printf("found %d at %d: ", x, ix);

		if (in_nrp[x]) {
			// Je v NRP => nepřesouváme
			// printf("in NRP\n");
			next = ix + 1;
		} else {
			if (next > ix)	// +/- 1: Přesun z pozice ix na ix+1 nic nestojí
				next--;
			// printf("move %d[%d] by %d\n", ix, x, next-ix);
			move_x[n_moves] = x;
			move_by[n_moves] = next - ix;
			n_moves++;
			s_remove(nodes[x]);
			s_insert(nodes[x], nodes[x-1]);
			next++;
		}
	}
}

/*** Testování ***/

// Vygeneruje náhodný vstup
void generate(void)
{
	for (int i=1; i<=n; i++)
		X[i] = i;
	for (int i=1; i<=n; i++) {
		int j = i + rand() % (n-i+1);
		int t = X[i];
		X[i] = X[j];
		X[j] = t;
	}
}

// Vypíše vstup
void show_in(void)
{
	printf("Input[%d]:", n);
	for (int i=1; i<=n; i++)
		printf(" %d", X[i]);
	printf("\n");
}

// Vypíše NRP
void show_nrp(void)
{
	printf("NRP[%d]:", n_nrp);
	for (int i=0; i<n_nrp; i++)
		printf(" %d(%d)", nrp[i], X[nrp[i]]);
	printf("\n");
}

// Vypíše nalezené přesuny a odsimuluje je
void show_moves(void)
{
	printf("Moves[%d]:\n", n_moves);
	assert(n_moves == n - n_nrp);
	for (int i=0; i<n_moves; i++) {
		int ix = 0;
		for (int j=1; j<=n; j++)
			if (X[j] == move_x[i])
				ix = j;
		int next = ix + move_by[i];
		printf("\t%d from %d to %d\n", move_x[i], ix, next);
		if (next < ix) {
			for (int i=ix; i>next; i--)
				X[i] = X[i-1];
		} else {
			for (int i=ix; i<next; i++)
				X[i] = X[i+1];
		}
		X[next++] = move_x[i];
	}

	printf("Sorted[%d]:", n);
	for (int i=1; i<=n; i++) {
		printf(" %d", X[i]);
		assert(i == 1 || X[i] > X[i-1]);
	}
	printf("\n");
}

// Hlavní program
int main(void)
{
	srand(42);
	n = MAXN;
	generate();
	show_in();

	find_nrp();
	show_nrp();

	find_moves();
	show_moves();

	return 0;
}