题意
做法
结论:有操作(up~v),设先前最大值为(u),则(u-v)这条路径将保留到最后,其他点相对顺序不变
证明:
保留到最后很显然;相对顺序不变听上去很显然,证的话就大力分类讨论,不过不是很优美
(up~v)时,将(u-v)打上个新的时间戳,路径内顺序为(ulongrightarrow ...longrightarrow v),这个可以通过LCT的(split)操作实现
块外就相当于查询比其时间戳小的点的个数,可以用BIT维护
结论:有操作(up~v),设先前最大值为(u),则(u-v)这条路径将保留到最后,其他点相对顺序不变
证明:
保留到最后很显然;相对顺序不变听上去很显然,证的话就大力分类讨论,不过不是很优美
(up~v)时,将(u-v)打上个新的时间戳,路径内顺序为(ulongrightarrow ...longrightarrow v),这个可以通过LCT的(split)操作实现
块外就相当于查询比其时间戳小的点的个数,可以用BIT维护