Link Cut Tree学习笔记

Link-Cut Tree 是用于维护由一组有根树组成的森林的数据结构,Link-Cut Tree 的基本操作复杂度为均摊 $O({\log_2}n)$ ,具体的定义和时间复杂度的证明可以移步
《QTREE 解法的一些研究》,这里主要介绍它的基本操作的具体实现。

「BZOJ-4571」[Scoi2016]美味

一家餐厅有 n 道菜,编号 1…n ,大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客,第 i 位顾客的期望值为 bi,而他的偏好值为 xi 。因此,第 i 位顾客认为第 j 道菜的美味度为 bi XOR(aj+xi),XOR 表示异或运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

「BZOJ-1305」dance跳舞最大流

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

「BZOJ-3262」陌上花开-CDQ分治

有$n$朵花,每朵花有三个属性:花形$(s)$、颜色$(c)$、气味$(m)$,又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花$A$比另一朵花$B$要美丽,当且仅当$S_a$>=$S_b$,$C_a$>=$C_b$,$M_a$>=$M_b$。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。