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

针对使用线段树做TLE的同学的提示!

Posted by yc5_yc at 2012-07-16 11:31:08 on Problem 2777
再查找过程中,我们一般是这样做的:
    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:
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