CF1137F Matches Are Not a Child's Play

题意

cf

做法

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

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

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

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