雅礼集训 Day6

 今日得分:10+0+20=30,修改后90+90+100=280

今日题解:

T1:题中所给的结构构成一个内向环套树森林,对于每棵环套树,首先树上的每个点的孩子只能留一个最大的,其他的都需要修改,处理后变为一个环上面连一些链,每个链可以断开链首或者断开环上的前驱节点,并且至少要断开一条环上的边,特判只有一个环的情况即可

T2:一个位置如果先吃掉左边的三明治,那么它左边的位置也会先吃左边,于是我们对于每一行的都搜一遍即可

T3:如果所有操作都是在1~n区间内进行,那么它的实际作用就是去掉最大值再加入一个新值,可以pq维护,我们考虑分块,对于每个块维护一个pq,如果某次操作整个覆盖了某个区间,我们对pq做相应处理并在这个块上打一个标记,现在只需要考虑如何下放标记即可,考虑对偶情况,我们对寿司维护一个堆,显然每个位置会把最小的寿司换出来,然后把自己丢进去,这样就可以klogk下放标记,总复杂度 O(qsqrt(n)logn)

后记:今天题目质量真高

原文地址:https://www.cnblogs.com/LoveYayoi/p/7071856.html