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:dieyidezui at 2014-05-13 20:03:50 > 也不用把每一张海报离散出4个点,用线段树的线段,而不是点段, > 一个简单的例子 > 3 > 1 10 > 1 3 > 6 10 > 用点离散化是不行的,这样离散后 > 就变 > 1 3 6 10 > 1 2 3 4 > 覆盖了 > 1 4 > 1 2 > 3 4 > 答案是2, > 其实是3. > 正确的做法是把1 3 处理成 0 3的线的端点 > 这样就变型为 > 0 10 > 0 3 > 5 10 > 线段树分段的时候就不是 > mid+1,r 和 l, mid了 > 而是 l,mid 和 mid,r > 这样就可以妥妥的AC 赞,我也这么想的~感觉左闭右开更舒服 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator