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: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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator