15919. Bajtokwasy [AL_10_03]

[slawus28]

Od dłuższego czasu zmagam się z tym zadaniem (pl.spoj.com/problems/AL_10_03/), niestety bezskutecznie. Zadanie polega na znalezieniu liczbie wszystkich monotonicznych 3 elementowych podciagów n-permutacji. Opracowane przeze mnie rozwiązanie wylicza dla każdego z elementów liczbę wartości mniejszych od niego, znajdujących się na lewo od niego. Znając tą wartość, możliwe jest obliczenie liczby elementów mniejszych znajdujących się na prawo, oraz liczbę elementów wiekszych (odpowiednio po lewej i prawej stronie). Dzięki temu, możliwe jest obliczenie liczby 3-elementowych monotonicznych podciągów, których środowy wyraz stanowi badany element.

Pomimo początkowych problemów z wydajnością, udało mi się napisać algorytm który korzysta z drzew czerwono-czarnych (bazuje na implementacji stąd: kicia.ift.uni.wroc.pl/algorytmy/RBtree.cc). Każdy z elementów drzewa posiada pole counter, określające liczbę wartości mniejszych od niej, która jest inkrementowana w momencie dodania elementów do drzewa.

Dla wszystkich problemów wymyślonych przeze mnie "ręcznie" algorytm daje wyniki identyczne jak brute-force, mimo to spoj zwraca mi "błędna odpowiedź ". Podejrzewałem problemy spowodowane przepełnieniem zmiennych więc wszystkie inty rozszerzone zostały do unsigned long, co nie stety nie przyniosło żadnego rezultatu. Prosiłbym o jakieś sugestie, bo już odchodzę od zmysłów

[bbone=CPP,1719]

include

struct node
{
int key;
bool b;
node* parent;
node* left;
node* right;
unsigned long long int counter;
node(int k,node* t, node* l, node* r, bool b0=0)
:key(k),b(b0),parent(t),left(l),right(r), counter(0)
{
}
bool black()
{
return b;
}
bool red()
{
return not b;
}
};

node nulll(-1,&nulll,&nulll,&nulll,1);
node *null=&nulll;

void rotate_right(node *& t, bool c1=1, bool c2=0)
{
node* n=t->left;
node* c=n->right;

t->counter =  0;

t->b=c1;
n->b=c2;

c->parent=t;
t->left=c;

n->parent=t->parent;		
n->right=t;
t->parent=n;

t=n;

}

void rotate_left(node *& t, bool c1, bool c2)
{
node* n=t->right;
node* c=n->left;

n->counter = t->counter + 1;

t->b=c1;
n->b=c2;

c->parent=t;
t->right=c;

n->parent=t->parent;		
n->left=t;
t->parent=n;
    
t=n;

}

int Insert(node*& t, int k)
{
unsigned long long int res = 0;
// insert into RB tree with fixup
if(t==null)
t=new node(k,null,null,null,1);
else
{
node x=t,y=null;
while(x!=null)
{
y=x;
if(k < x->key)
{
x->counter++;
x=x->left;
}
else
{
res += x->counter + 1;
x=x->right;
}
}
if(kkey)
y->left=x=new node(k,y,null,null);
else
y->right=x=new node(k,y,null,null);

	/// node inserted 
	/// now we do tree fixup
	while(y!=null && y->red())
	{
		node* z=y->parent;
		if(z->left->b == z->right->b)
		{	
			z->left->b=z->right->b=true;
			z->b=false;
			x=z;
			y=z->parent;
		}
		else 
		{ 
			bool yz=y==z->right;
			bool xy=x==y->right;
			if(yz != xy)
			{ if(yz)
				rotate_right(z->right,0,0);
			  else		
				rotate_left(z->left,0,0);
			}
			node*& Z= z==t? t :(z==z->parent->left ? z->parent->left :z->parent->right); 
			if(yz)
				rotate_left(Z,0,1);
			else	
				rotate_right(Z,0,1);
			break;
		}
	}
	t->b=true;	
} 

return res;

}

int main()
{
unsigned long int t, n;

fscanf(stdin, "%ld", &t);
for(int i = 0; i < t; i++)
{
    fscanf(stdin, "%ld", &n);

    unsigned long long int res = 0;
    node* t=null;

	for(int index = 0; index < n; index++)
	{
        unsigned long val;
		fscanf(stdin, "%ld", &val);

        unsigned long long int smallerOnLeft = Insert(t, val);
        unsigned long long int smallerOnRight = val - smallerOnLeft - 1;
        unsigned long long int biggerOnLeft = index - smallerOnLeft;
        unsigned long long int biggerOnRight = n - val - biggerOnLeft;

        res += smallerOnLeft * biggerOnRight + smallerOnRight*biggerOnLeft;
	}
    
    fprintf(stdout, "%lld\n", res);
}


return 0;

}
[/bbone]