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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

这样离散不会有问题

Posted by haiwei624 at 2010-01-16 17:49:56 on Problem 2528 and last updated at 2010-01-16 17:50:11
In Reply To:Re:我觉得离散化会有问题 Posted by:heimengnan at 2009-11-23 10:03:30
> 
> 
> 我觉得吧。。你这样也不对 如果我插入
> 
> 4
> 1 3
> 1 1
> 2 2
> 3 3
> 这样的数据 怎么办..? o(╯□╰)o

貌似问题不大。右端点+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