#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int a[51000];
typedef struct node
{
int a,b;
int MIN,MAX;
struct node *lchild,*rchild;
}Itree;

Itree *R;

Itree *creat(int x,int y)
{
int mid;
Itree *r;
if (x>=y) return NULL;
else
{
   r=new Itree;
   r->a=x;
   r->b=y;
   if (y-x>1)
   {
   r->lchild=creat(x,(x+y)/2);
   r->rchild=creat((x+y)/2,y);
   }
   else
   {
   r->lchild=NULL;
   r->rchild=NULL;
   }
   if ((y-x)==1)
   {
     if (a[x]>a[y])
	 {
	   r->MAX=a[x];
	   r->MIN=a[y];
	 }
     else
	 {
	   r->MAX=a[y];
	   r->MIN=a[x];
	 
	 }
   }
   else
   {
    if (r->lchild->MAX>r->rchild->MAX)
	 r->MAX=r->lchild->MAX;
	else
	 r->MAX=r->rchild->MAX;
	if (r->lchild->MIN<r->rchild->MIN)
	 r->MIN=r->lchild->MIN;
	else
	 r->MIN=r->rchild->MIN;
   }
}
return r;
}

int fMAX(Itree *H,int x,int y)
{
int mid,t1,t2;
if (H)
{
if (x<=H->a && H->b<=y) return H->MAX;
else
{
mid=(H->a+H->b)/2;
if (y<=mid) return fMAX(H->lchild,x,y);
else
{
if (x>=mid) return fMAX(H->rchild,x,y);
else
{
t1=fMAX(H->lchild,x,mid);
t2=fMAX(H->rchild,mid,y);
if (t1>t2) return t1;
else return t2;
}
} 
}
}
}

int fMIN(Itree *H,int x,int y)
{
int mid,t1,t2;
if (H)
{
if (x<=H->a && H->b<=y) return H->MIN;
else
{
mid=(H->a+H->b)/2;
if (y<=mid) return fMIN(H->lchild,x,y);
else
{
if (x>=mid) return fMIN(H->rchild,x,y);
else
{
t1=fMIN(H->lchild,x,mid);
t2=fMIN(H->rchild,mid,y);
if (t1<t2) return t1;
else return t2;
}
} 
}
}
}


int main()
{
int i,t1,t2;
scanf("%d %d",&n,&q);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
R=creat(1,n);
for(i=1;i<=q;i++)
{
scanf("%d %d",&t1,&t2);
printf("%d\n",fMAX(R,t1,t2)-fMIN(R,t1,t2));
}
return 0;
}

• Re:第一个线段树怎么3000多ms大牛们帮我看看啊，太慢了 (29) ssadwlll 2008-07-26 12:50:20
  • Re:第一个线段树怎么3000多ms大牛们帮我看看啊，太慢了 (48) Millky 2008-07-30 09:56:52
    • new 会慢不少的。。 改成静态点，就会快～～ (0) kamel52045386 2008-07-30 10:07:18
• Re:第一个线段树怎么3000多ms大牛们帮我看看啊，太慢了 (8) D00095 2008-10-11 16:44:11
  • Re:第一个线段树怎么3000多ms大牛们帮我看看啊，太慢了 (7) ACM_henry 2008-10-11 16:46:57