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 cscaoshang at 2011-09-24 22:00:40 on Problem 1944
In Reply To:线段树写烂了,不过速度还可以,也说一下做法吧 Posted by:dongshanluo at 2011-09-24 15:44:24
> 转换一下,把长度为n的环解开变成一条链,再复制一变,变成一个长度为2n的链条,取前2n-1个结点,那么枚举断点方法里的任何一种种断点对应到的就是2n-1个结点里的一个长度为n的链条了;
> 
> 把输入把P个组成对儿,
> 对于每个输入对x < y,折成3条线段
> x -> y
> y -> x + n
> x + n -> y+n
> 开始的时候把所有x ->y的线段插入到线段树里,边读入数据边插入,这时会插入P条线段了
> 查询一下线段树里1->n被覆盖的长度就是从1与n之间断开的解了
> 接下来就是从1 与2之间断开,
> 把1->y的所有线段都删掉,同时把y->n+1的线段插入到线段树里边,完成之后查询2->n+1被覆盖的长度就是从1 与2之断开的解了
> 如此下去,就能得到解了

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