10月做题记录

10月做题记录
最后一个10月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

这个月主要在做课件,整体质量不错

loj2049「HNOI2016」网络

请先思考后再展开

做法一(在线,$O(nlog^3n)$):无脑树剖+线段树,每个节点开可删堆

做法二(离线,$O(nlog^3n)$):无脑线段树分治+树剖+线段树

做法三(离线,$O(nlog^2n)$):考虑二分,转化为判断是否所有路径都经过x,考虑路径交;依然线段树分治,预处理线段树每个节点权值顺序后缀路径交(这部分两个log),每次在上面log个节点上二分后取max

做法四(离线,$O(nlog^2n)$):整体二分,支持插入删除维护路径交就是一个差分+树状数组求子树和来判断次数是否和所有相等

做法五(在线,$O(nlogn)$):直接二分,求时间前缀的、后缀值域的路径交,值域线段树上二分即可

HDU6634 Salty Fish

请先思考后再展开

明显最小割(割苹果表示舍弃,割监控表示hack),转化为求最大流

注意到是个二分图,而且连边的形式很特殊,范围又特别大,考虑贪心i am the king

注意到每次都会优先流深度最深的可以流的节点,将入边放到树上,等于每次找深度范围内能搞的流出去

注意到对于子树内的出边,只和深度有关,考虑长链剖分,搞个map存每个深度,还没有流完的,借助upper_bound和erase可以保证复杂度即$O(nlogn)$,code

CF997E Good Subsegments

请先思考后再展开

这题似乎可以析合树,然而我并不会构造树,就不这样搞了;口胡一下另一种做法

注意到允许离线,那么把询问挂在右端点上,对于每个右端点给其合法左端点打上标记,那么回答询问就是查询这个和

连续段满足$min(mx-mi+l)=r$,所以维护好这东西的话就可以用线段树给最小值位置打标记

mx和mi可以通过单调栈找到并更新,需要支持区间加减(这样应该更好维护?),区间询问标记和,应该可以$O(nlogn)$

HDU5709 Claris Loves Painting

题意:n个有色点的树,q次询问一个点的子树中与这个点距离不超过d的点的颜色有多少种,强制在线,$\sum n,\sum q \le 5e5$

请先思考后再展开

数颜色题可能有个套路是每个颜色贡献到它第一次出现

先求出每个子树内,某个颜色第一次出现的位置,可以用启发式合并map求,$O(nlog^2n)$

但现在要计数的话,就是区间询问在这个深度出现的颜色数,直接合并肯定是不行的,但我们可以在做上面那玩意的时候,如果发现重复颜色修改对应深度颜色数,这样的修改只有颜色数即n次,然后每个深度的颜色数也用启发式合并map的话,也是$O(nlog^2n)$

复杂度不优秀而且是离线算法,将两个启发式合并都改成线段树合并,这样就是$O(nlogn)$的,code

CF1209G2 Into Blocks

题意:长度为n的序列,q次单点修改后询问序列美丽值。美丽值为通过每次修改某颜色所有位置为另一颜色,最后使得整个序列任意颜色都是连续一段,的最小修改量,$n,q\le 2e5$

请先思考后再展开

首先很明显easy就是让我们找到不带修时的做法,挖掘一些性质然后hard用一些数据结构维护,然而我还是不会

对于无修改,设值c的出现区间为$[fl_c,fr_c]$,最后$fl_c…fr_c-1$都要和下一个相同,设$f_i$为被如此统计的次数

那么$f_i=0$的位置就是一个段的结尾,将每种颜色的出现次数贡献到最左边的位置并记为$cnt_i$

$ans=n-\sum_{每个段} cnt[fl_{出现最多次的值}]$,现在就是对这玩意求和,无修改直接扫一遍即可。

考虑线段树能否维护,【最小值为0维护以0分割连续段的信息】经典转化成【区间以最小值分割的连续段的信息】

其实已经可以做了,如果你还是不会维护可以继续往下看,用一棵还是两棵线段树维护无所谓

我们只需要保证对于$mif=0$的区间算出的信息是正确的,设一个段$[kl,kr]$,记区间询问最大cnt为变量mxc,然后区间所有段的mxc和为sum,mif不为0的区间得出的sum并没有直接意义

如何合并两侧的信息?发现需要记录$mif、mif最左边的点mifl、最右边的点mifr$

对于两侧最小值不同的情况:

$sum[x]=sum[lc]+sum[rc]-mxc(mifr[lc]+1..mid)-mxc(mid+1..mifl[rc])+mxc(mifr[lc]+1..mifl[rc])$

若$mif[lc]<mif[rc]$:$sum[x]=sum[lc]-mxc(mifr[lc]+1,mid)+mxc(mifr[lc]+1,r)$

若$mif[lc]>mif[rc]$:$sum[x]=sum[rc]-mxc(mid+1,mifr[rc])+mxc(l,mifr[rc])$

最后$ans=n-sum[root]$,修改就是【单点改cnt而改mxc,更新包含这个点的区间的f和sum】、【区间加减f,sum不变,记录加法标记tag即可】

维护sum需要调用log次查询mxc,$O(qlog^2n)$,code

CF97E Leaders

题意: n个点m条边的简单无向图,q次询问两点间是否存在长度为奇数的简单路径,$n,m,q \le 1e5$

请先思考后再展开

两点间路径会想到处理出一棵生成树,那肯定是选择dfs搜索树方便,因为没有横叉边

结论:对于无向图,一个点双内如果有奇环,那么内部每条边都至少在一个奇环中;点双内有奇环的充要条件是在dfs搜索树上存在一个【一条非树边+若干树边】组成的奇环;

两个点间存在奇数长度简单路径的充要条件是:两点树上距离为奇数、两点树上路径中至少一条边在至少一个奇环中

两个点间存在偶数长度简单路径的充要条件是:两点树上距离为偶数、两点树上路径中至少一条边在至少一个奇环中

于是求v-DDC,树上差分即可

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d9e23b83.html
转载请注明出处,谢谢!