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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:无语……

Posted by NtNlyCoder at 2015-10-10 01:17:23 on Problem 2828
In Reply To:无语…… Posted by:liuaohanjsj at 2013-04-27 16:50:24
> 理论上如果你用的是完全二叉树结构,3*200000都应该WA的。
> 完全二叉树结构理论要开 4*n;
> 只有指针结构的才能开2*n.
> 真是无语了……
感觉理论上3*N是上限额,不需要开到4*N吧。线段树区间长度为2的幂是,是满二叉树,有lgN层,其他情况都是lgN + 1层,应为会有3分成2和1;2再分成1和1的类似情况;一个长度为N的区间不可能划出超过N/2个长度为3的区间,长度为3的区间会在下一层多分出两个长度为1的区间,所以多出顶多N个节点。。所以感觉开3*N妥妥的够了。2*N是下限。

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