首页 > 其他 > 详细

CF1137F Matches Are Not a Child's Play

时间:2020-02-22 12:15:08      阅读:55      评论:0      收藏:0      [点我收藏+]

题意

cf

做法

结论:有操作\(up~v\),设先前最大值为\(u\),则\(u-v\)这条路径将保留到最后,其他点相对顺序不变

证明:
保留到最后很显然;相对顺序不变听上去很显然,证的话就大力分类讨论,不过不是很优美

\(up~v\)时,将\(u-v\)打上个新的时间戳,路径内顺序为\(u\longrightarrow ...\longrightarrow v\),这个可以通过LCT的\(split\)操作实现
块外就相当于查询比其时间戳小的点的个数,可以用BIT维护

CF1137F Matches Are Not a Child's Play

原文:https://www.cnblogs.com/Grice/p/12344122.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!