Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这样离散不会有问题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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator