Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请教过了的高手一个问题:为什么这题我用线段树来做时效率那么低?? 比直接做效率都低,而只能用树状数组来做? 下面是我的线段树代码

Posted by rruucc at 2003-09-29 10:52:14 on Problem 1341
#include<stdio.h>
#include<string.h>
#define MaxN 50001
#define MaxL 150001
#define Mod 9973
#define Type __int64
#define MinNum(a,b) ((a)>(b)?(b):(a))
#define MaxNum(a,b) ((a)>(b)?(a):(b))

int n,a1,a2,a3,m,s1,s2,s3,e1,e2,e3;
int a[MaxN],tp[MaxL],maxr,ans;

int build(int p,int s,int t)
//插入点
{ int lc=p*2+1,rc=p*2+2,mid=(s+t)/2;
 if (s==t)
  tp[p]=a[s];
 else
  tp[p]=MinNum(build(lc,s,mid),build(rc,mid+1,t));
 return tp[p];
}

int min(int p,int ss,int tt,int s,int t)
//求解最小
{ int lc=p*2+1,rc=p*2+2,mid=(s+t)/2,tmp;
 if (ss<=s&&tt>=t) return tp[p];
 else
  {tmp=Mod;
   if (ss<=mid) tmp=MinNum(tmp,min(lc,ss,tt,s,mid));
   if (tt>=mid+1) tmp=MinNum(tmp,min(rc,ss,tt,mid+1,t));
   return tmp;
  }
}

void getready()
{ Type i,tmp;
 for (i=0; i<n; i++)
  {tmp=(i*i*a1+i*a2+a3); tmp%=Mod; a[i]=int(tmp);}
 memset(tp,-1,sizeof(tp));
 build(0,0,n-1);
}

void search()
{ Type i,tmp;
  int s,e;
 maxr=-1;
 for (i=0; i<m; i++)
  {tmp=(i*i*s1+i*s2+s3); tmp%=(n/2); s=int(tmp);
   tmp=(i*i*e1+i*e2+e3); tmp%=(n/2); e=s+int(tmp);
   tmp=min(0,s,e,0,n-1);
   if (tmp>maxr) {maxr=int(tmp); ans=int(i);}   
  }
}

void show()
{printf("%d\n",ans);}

int main()
{ int testdata,i;
 scanf("%d",&testdata);
 for (i=0; i<testdata; i++)
  {scanf("%d%d%d%d%d%d%d%d%d%d%d",&n,&a1,&a2,&a3,&m,&s1,&s2,&s3,&e1,&e2,&e3);
   getready();
   search();
   show();
  }
 return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator