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

终于过了,线段树写各种炸,调了半天,有些细节请看此处

Posted by std_algorithm at 2018-02-28 07:32:19 on Problem 3225
1.首先把集合操作映射到线段树的01状态,对每个区间进行划分;
错误:常年不用switch忘了写break(x
2.线段树支持两种操作:区间覆盖和区间全部反转:两种lazy标记会冲突!!!
建议:在覆盖前pushdown反转,因为覆盖操作可以盖掉反转,而反转遇到覆盖时应该先执行覆盖,会出现同一节点两种lazy冲突,所以建议让每个节点优先执行反转,在向下更新前如果有本应先执行的覆盖操作提前计算并pushdown;
错误:边界条件炸了。。。
(卡掉我的一组discuss数据:
S [34403,38025)
I (16717,36429]
ans:[34403,36429] 
因为边界忘了处理,我输出了他们的父节点。。。)
3.别老粘板子!!!
错误:我的板子里pushdown遇到标记为0会返回,没法覆盖啊!!!!!!!!!
(样例都过不了)
4.听说有不合法数据,要判断(并作出相应处理!!!不要直接忽视!!!对空集要谨慎处理!!!)

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