用线段树搞了一下午都是TLE，用树状数组十分钟解决，靠，
这是我的TLE的线段树代码：
#include<iostream>
#include<string>
#include<fstream>
using namespace std;

int Sum[16000];

typedef struct STAR
{
    int   left;
     int right;
     int cover;  
    STAR   *leftchild;
    STAR   *rightchild;    
};

STAR * build(int   l ,  int r ) 
{
    STAR *root=new STAR;
	root->cover=0;
    root->left = l;
    root->right = r;     
    root->leftchild = NULL;
    root->rightchild = NULL;

    if ( l +1<= r )
    {
       int  mid = (r+l) /2;
       root->leftchild = build ( l , mid ) ;
       root->rightchild = build ( mid+1  , r) ; 
    } 

    return   root; 
}

void bianli(STAR *root)
{
	if(root!=NULL)
	{	 
		printf("%d-%d\n",root->left,root->right);
		bianli(root->leftchild);
		bianli(root->rightchild);
	}
}

void  Insert(int c, int d , STAR  *root )
{     
	if(root==NULL) return ;
	int mid=(root->left+root->right)/2;
	if(c==root->left&&d==root->right) 
		root->cover++;
    else
	{	
		root->cover++;
		if(d<=mid)
			Insert(c,d,root->leftchild);
		else if(c>mid)
			Insert(c,d,root->rightchild);
	}
}

int  Count(STAR *root,int c,int d)
{
    int  mid;
	if(root==NULL) return 0;
	mid=(root->left+root->right)/2;
	if(root->left==c&&root->right==d)
		 return root->cover;
	else
	{
	    if(d<=mid)
			return Count(root->leftchild,c,d);
		 else 
		 {
			return Count(root->leftchild,c,mid)+Count(root->rightchild,mid+1,d);
		 }
	}	
}

void shanchu(STAR *root,STAR *p1,STAR *p2){
	if(root!=NULL)
	{
		p1=root->leftchild;
	    p2=root->rightchild;
	    free(root);
		shanchu(p1,p1,p2);
		shanchu(p2,p1,p2);
	}
}

int main()
{
	int n,i,j,x,y,s;
	STAR *root;
	scanf("%d",&n);
	root=build(0,32100);
	for(i=0;i<n;i++)
		Sum[i]=0;
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		s=Count(root,0,x);
		Sum[s]++;
		Insert(x,x,root);
	}
	for(i=0;i<n;i++)
		printf("%d\n",Sum[i]);
	return 0;
}

• Re:50题留念~线段树无限TLE，果然树状数组更适合我 (2177) 131310220 2014-11-01 12:03:28