| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
针对使用线段树做TLE的同学的提示!再查找过程中,我们一般是这样做的:
if(b<=p->m)
sum(a,b,p->left);
else if(p->m<a)
sum(a,b,p->right);
else {
sum(a,p->m,p->left),sum(p->m+1,b,p->right);
}
于是可以证明,当前线段p一定包裹了[a,b]!
然而在前面,我们习惯于这样做:
if(p->l>=a && p->r<=b && p->color!=-1)
{
A[p->color]=1;
return ;
}
这样其实就等价于:
if(p->l==a && p->r==b && p->color!=-1)
{
A[p->color]=1;
return ;
}
如果像上面那样,我们每次查找就相当于走了几乎整棵树!时间复杂度必定很高!
由于前面我们证明的结果,我们何必不这样?
if(p->color!=-1)
{
A[p->color]=1;
return ;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator