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