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 ZhangChi at 2006-02-20 00:43:25 on Problem 2155
In Reply To:汗,怎么我用线段树就死TLE呢~~ Posted by:zhangchi at 2006-02-19 01:34:45
经过本人不懈努力,终于将此提AC,写下一点经验:
使用线段树会有很多种方法,这里有一些:
1 :使用4分的思想实现二维的线段树,据xreborner大牛说,此方法TLE
2 :使用二分的思想来实现,每次划分X轴或者Y轴,据本人实验,此方法还是TLE
3 :使用嵌套的线段树,先用X轴划分然后每个节点再包含一个线段树划分Y轴,此方法AC

上述每个方法实现的复杂度都是TlogN^2,当然也可能是本人代码丑陋,没有把方法2写的很优化,不过对于想AC的朋友来说,方法3是不错的选择 ^_^

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