「SDOI / SXOI2022」无处存储
链加链求和。
考虑先搞出随机撒点,然后建虚树,这样比较好维护一点。
然后就是正常的整块打 tag,散块暴力加之类的。
我写的好麻烦/kk
「LibreOJ Round #11」Misaka Network 与 Accelerator
我们考虑暴力 2-SAT,最多要连 \(O(n^2)\) 条边,时间空间都接受不了。
如果是点分治的话一个点要向其他子树的所有符合条件的点连边,时空复杂度还是不对。
然而如果是边分治,从一个点只向对面的一棵子树连边,也就是一次只会用到两个子树,那么每次只需要搞两颗线段树,然后直接连就可以了。
然后还是要搞清 2-SAT 的连边方式的/kk
我错了,我不会边分治,【数据删除】,我真的错了。
CF662B Graph Coloring
没有水平
我们考虑如果固定一个点是否反转,与它相邻的点是否反转是固定的。所以转化成 2-SAT,然后考虑如果反转一个点,那么整张图都会反转。所以假设要把整张图染成红色的,那么就连一个 2-SAT 的图出来,然后跑一边是否合法以及如果第一个点不反转需要转多少个点。
反转无脑 2-SAT 就对了。
[CTSC2008] 网络管理
没有水平题。
先整体二分一下,然后就是链求和。但是这样好像是 \(O(n\log ^3 n)\) 的。
所以我们考虑把所有的加法转化成子树加,然后求和是单点求和,求出的是自己到根的值,然后求个 lca 减一下就行。
这样能换成树状数组。复杂度 \(O(n\log ^2 n)\)。
标签:连边,Set,一个点,反转,Solution,然后,子树,SAT From: https://www.cnblogs.com/cc0000/p/17524930.html