笛卡尔树以及treap---zoj_2243

        zoj_2243笛卡尔树的构造，开始被topcoder上的教程吸引去看这题。题目中说这种数据结构叫treap然后就按照treap的insert加上左旋右旋去做了，结果果断TLE。然后网上找了一下关于笛卡尔树的资料，发现了一些问题的端倪。

       首先，treap和笛卡尔树从形式上来说是完全一样的，即是一颗二叉搜索树和二叉堆的结合（不是严格意义上的二叉堆，因为二叉堆是一颗完全二叉树，而treap不是）。但是他们的目的也许不太一样。treap更大的意义在于为了维持BST的平衡型而找到的一种随即化构造的方案。在treap中，insert的时候节点的value值是随机生成的。因此在逐个insert节点的时候能够保证treap的统计意义上的平衡。然而，笛卡尔树的目的更多是为了rmq问题和LCA问题的转化。

       其次，我们可以看到，在zoj_2243中，如果使用treap,按照题意一个个插如节点，随即化就被打破了，judge系统的数据也许不随机，从而导致treap的链化，弱化了平衡性，理想的NlogN的复杂度，可能退化到N^2，导致最后的TLE（可能左旋右旋操作的消耗也对应能有所影响）.

       最后，找到了一种排序之后直接构造笛卡尔树的方法。首先将节点序列按照key从小到大排序，然后按照顺序插入节点，注意到排序之后，插入的节点的key值一定是树中最大的，所以只需查找最右端的路径，找到一个节点A[i]的value大于待插入节点的value,同时A[i]->right的value小于待插入节点的value。找到之后，只需将A[i]的right指向待插入的节点，A[i]的right原来指向的节点赋值给待插入节点的left指针。注意到查找最右路径的方向，如果从下到上查找，复杂度比较容易分析O(N)（因为查找过的节点必然会旋转到某个节点的左子节点，因此每个查找过的节点只会被查找一次），如果从上倒下，比较复杂（和最右端的最终的路径长度有关吧），会超过N，甚至更高，可能为O(N^2)。

       另外，找到一种使用排序加左旋的方法，就是一样先排序，然后使用treap插入节点，可以发现，所有的旋转都为左旋。这种方法也TLE了，这种方法有一个很重要的意义，就是分析了上个方法中从上到下扫描的复杂度。因为这两种方法的效率是等价的，都TLE。

       最后，同样的题ZOJ是5M的，POJ是2M的，我用了从上到下2.5S，从下到上0.6S。

代码zoj_2243

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
class treap_node
{
public:
	string label;
	int p;
	treap_node* left;
	treap_node* right;
	treap_node()
	{
		left=NULL;
		right=NULL;
	}
};
class treap
{
	public:
	treap_node*root;
	treap()
	{
		root=NULL;
	}
	void treap_left_rotate(treap_node*&a)
	{
		treap_node*b=a->right;
		a->right=b->left;
		b->left=a;
		a=b;
	}
	void treap_right_rotate(treap_node*&a)
	{
		treap_node*b=a->left;
		a->left=b->right;
		b->right=a;
		a=b;	
	}
	void treap_insert(treap_node*&a,string label,int p)
	{
		if(!a)
		{
			a=new treap_node;
			a->label=label;
			a->p=p;
		}
		else if(label<a->label)
		{
			treap_insert(a->left,label,p);
			if(a->left->p>a->p)
				treap_right_rotate(a);
		}
		else
		{
			treap_insert(a->right,label,p);
			if(a->right->p>a->p)
				treap_left_rotate(a);
		}	
	}
	void plist(treap_node*a)
	{
		if(a!=NULL)
		{
		cout<<"(";
		plist(a->left);
		cout<<a->label<<"/"<<a->p;
		plist(a->right);
		cout<<")";
		}	
	}	
};
int num;
treap_node n[50001];
bool cmp(const treap_node&n1,const treap_node&n2)
{
	return n1.label<n2.label;
}
void insertN(treap_node*&p)
{
	for(int i=0;i<num;i++)
	{
		treap_node* pre=NULL;
		treap_node* tmp=p;
		while(tmp!=NULL&&tmp->p>n[i].p)
		{
			pre=tmp;
			tmp=tmp->right;	
		}
		if(pre==NULL)
		{
			treap_node* node=new treap_node;
			node->label=n[i].label;
			node->p=n[i].p;
			p=node;
			p->left=tmp;
		}
		else
		{	treap_node* node=new treap_node;
			node->label=n[i].label;
			node->p=n[i].p;
			pre->right=node;
			node->left=tmp;
		}
	}	
	return;
}
int main()
{
	freopen("e:\\zoj\\zoj_2243.txt","r",stdin);
	while(cin>>num&&num)
	{
		treap* p=new treap;
		getchar();
		for(int i=0;i<num;i++)
		{
			char c[1000];
			int pi;
			scanf("%[^/]s",c);
			scanf("/%d",&pi);
			getchar();
			string str;
			str.append(c);
			treap_node node;
			node.label=str;
			node.p=pi;
			n[i]=node;
			//p->treap_insert(p->root,str,pi);	
		}
		sort(n,n+num,cmp);
		//for(int i=0;i<num;i++)
		//	p->treap_insert(p->root,n[i].label,n[i].p);
		insertN(p->root);
		p->plist(p->root);
		cout<<endl;	
	}
	return 0;
}