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 Qinz at 2009-02-23 13:03:24 on Problem 2528 and last updated at 2009-02-23 16:55:06 
先离散化，再从左到右扫描，检查每个离散点是什么颜色并统计
至于判断每个点是什么颜色可以用一个最大堆来实现：由于染色是从第0种颜色开始到第n-1种，故表层的颜色一定是最大的。通过维护最大堆，进扫描线的入堆，出扫描线的出堆，可以在O(lgn)时间内知道当前离散点的颜色
PS：3277题思路跟这差不多，也可以用最大堆
PS2：其实发本贴的根本目的是要纪念我的100AC。。。
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