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

Re:这样离散不会有问题

Posted by Mghost at 2010-09-07 17:03:58 on Problem 2528
In Reply To:这样离散不会有问题 Posted by:haiwei624 at 2010-01-16 17:49:56
> 
> 貌似问题不大。右端点+1就相当于把区间用区间左右的两个点表示,而这样做肯定没问题是因为点是完全可以离散的。
> 上面数据转化成用两端点表示后变成:
> 4
> 1 4
> 1 2
> 2 3
> 3 4
> 
> 然后,我们在做线段树的时候,再把它转回到区间的形式,也就是右端点再减14
> 1 3
> 1 1
> 2 2
> 3 3
> 这样就是离散后的与题目输入格式相同的数字i代表第i个区间的表示方式。
> 
> 
> 
> 虽然绕圈子,但是避免了直接把一段段区间拿去离散带来的错误。最初的
> 1 10
> 1 3
> 6 11
> 按这种逻辑更严谨的离散方法离散后就是:
> 1-3
> 1-1
> 3-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