我的程序：用二叉排序树做的
#include<stdio.h>
#include<stdlib.h>
#define maxstar 15001
typedef struct star
{
	int date;
	int lev;
	int lchild,rchild;
	};
	
	int root=-1;
	int level;
	int num[maxstar];
	star stars[maxstar];
	
 void insert(int x,int i)
  {
	  int p,q;
	   p=i;
	  if(root==-1)
	   {root=0;stars[root].date=x;stars[root].lev=1;stars[root].lchild=-1;stars[root].rchild=-1;num[level]++;return;}
	   
	   q=root;
	  while(1)
	   {
		   if(stars[q].date==x)
		     {level+=stars[q].lev;num[level]++;stars[q].lev++;return;}
		   if(stars[q].date>x)
		     {
			     if(stars[q].lchild!=-1)
			       {stars[q].lev++;q=stars[q].lchild;continue;}
			     else {stars[q].lev++;stars[q].lchild=p;stars[p].date=x;stars[p].lchild=-1;stars[p].rchild=-1;stars[p].lev=1;num[level]++;return;}
			   }
			  if(stars[q].date<x)
		     {
			     if(stars[q].rchild!=-1)
			       {level+=stars[q].lev;q=stars[q].rchild;continue;}
			     else {level+=stars[q].lev;stars[p].date=x;num[level]++;stars[q].rchild=p;stars[p].lchild=-1;stars[p].rchild=-1;stars[p].lev=1;return;}
			   }      
	 }  
		   
		   
		   } 
		   
	int main()
	{  int x,y,n,i;
		scanf("%d",&n);
		for(i=0;i<=n-1;i++)
		 {
			 scanf("%d%d",&x,&y);
			 level=0;
			 insert(x,i);
			 }
	for(i=0;i<=n-1;i++)	
	 printf("%d\n",num[i]);	
		}

• 怀疑bst会退化，O(n^2)就挂了 (1459) frkstyc 2006-01-11 18:29:13
  • Re:怀疑bst会退化，O(n^2)就挂了 (0) fxzy 2006-01-11 19:13:19
    • Re:怀疑bst会退化，O(n^2)就挂了 (9) fxzy 2006-01-11 19:13:43
• Use bbst instead of bst. It's available. (0) oooooo 2006-01-28 10:12:03
  • 我的平衡树，怎么交都交不到100ms以内~ 我写的线段树野蛮。 (0) PIGHEAD 2006-02-08 21:23:53
    • 也慢 (0) PIGHEAD 2006-02-08 21:24:25