问一下，Treap咋写啊？我的超时。

#define MAXNUM 1000001
#include "stdio.h"
#include "time.h"
#include "stdlib.h"
int maxV[MAXNUM],minV[MAXNUM];
int data[MAXNUM];
struct Treap
{
	int val,prio;
	Treap *lc,*rc,*parent;
	void insert(int v);
	void rotate();
	void del(int v);
	int getmin();
	int getmax();
};
Treap root;
int n,k,i;
int main(int argc, char* argv[])
{
	srand(time(0));
	root.prio=1<<31;root.val=1<<31;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;++i)
		scanf("%d",&data[i]);
	for(i=0;i<k;++i)
		root.insert(data[i]);
	for(i=0;i<n-k;++i)
	{
		minV[i]=root.getmin();
		maxV[i]=root.getmax();
		root.del(data[i]);
		root.insert(data[i+k]);
	}
	minV[i]=root.getmin();
	maxV[i]=root.getmax();
	for(i=0;i<=n-k;++i)
		printf("%d ",minV[i]);printf("\n");
	for(i=0;i<=n-k;++i)
		printf("%d ",maxV[i]);printf("\n");
	return 0;
}

void Treap::rotate()
{
	Treap* pp=parent->parent;
	if(parent->rc == this)
	{
		parent->rc = lc;
		if(lc)
			lc->parent=parent;
		if(pp->lc == parent)
			pp->lc=this;
		else
			pp->rc=this;
		lc = parent;
		parent->parent = this;
		parent = pp;
	}
	else
	{
		parent->lc = rc;
		if(rc)
			rc->parent=parent;
		if(pp->rc == parent)
			pp->rc=this;
		else
			pp->lc=this;
		rc = parent;
		parent->parent = this;
		parent = pp;
	}
}
void Treap::insert(int v)
{
	Treap* p=this,*q;
	while(p!=NULL)
	{
		q=p;
		if(p->val>v)
			p = p->lc;
		else
			p = p->rc;
	}
	Treap* node = new Treap;
	node->val = v; node->prio=rand();node->lc=node->rc=NULL;node->parent=q;
	if(q->val>v)
		q->lc= node;
	else
		q->rc=node;
	while(node->prio<node->parent->prio)
		node->rotate();
}
void Treap::del(int v)
{
	Treap* p=this,*q,*r;
	while(p->val!=v)
		if(p->val>v)
			p=p->lc;
		else
			p=p->rc;
	if(p->lc==NULL)
	{
		q=p->rc;
		if(p->parent->rc == p)
			p->parent->rc = q;
		else
			p->parent->lc = q;
		if(q)
			q->parent = p->parent;
		delete p;
	}
	else
	{
		q=p->lc;
		while(q!=NULL)
		{
			r=q;q=q->rc;
		}
		p->val = r->val;
		if(r==p->lc)
			p->lc = r->lc;
		else
			r->parent->rc= r->lc;
		if(r->lc)
			r->lc->parent = r->parent;
		delete r;
	}
}
int Treap::getmax()
{
	Treap* q=this;
	while(q->rc) q=q->rc;
	return q->val;
}
int Treap::getmin()
{
	Treap* q=rc;
	while(q->lc) q=q->lc;
	return q->val;
}

• 此题不用Treap/线段树/RMQ等 (29) lsz2008 2008-06-20 07:58:49