玄学算法/精彩DS总结 Vasuku

## $31.Complementary\ Graph$ 一种BFS可以在$O(m)$的复杂度遍历出它补图的连通块个数及大小。过程如下： 1. 建立一个链表把所有点连起来，然后随便从链表中找一个点BFS。 2. 对于当前队首，将所有链表里没有与它连边且未被$visit$的点$push$进队列，并将它们从链表中删除并标记为$visited$。 3. 重复此过程进行多次BFS直到链表为空。在删除一个点的时候就可以顺便统计信息了。 复杂度证明的话，一条边最多会被经过两次，所以显然是最坏$O(m)$的。 对于多组询问，假设询问$K=\sum k$ ，如果要把复杂度卡到$O(m)$，至少需要运用到$O(\sqrt{m})$个点构造一个完全图也就是$O(\sqrt{m}^2)=O(m)$才能卡满，所以最多询问$O(\frac{K}{\sqrt{m}})=O(\sqrt{m})$次（假设$K,m$同阶），也就是说复杂度不会超过$O(m\sqrt{m})$。 实现上，判断是否有连边可以开个哈希表，**注意遍历这个点的边作标记复杂度是错误的。** ## $32.Segment\ Tree\ Dividing\&Conquering$ （时间）线段树分治是一种离线思想，是把处理目标的存在时间的区间映射到线段树上，再利用一个可撤销的数据结构进行整体地回答问题与处理影响。 狭义上来说，线段树分治是考虑左边对右边的贡献，与CDQ分治是相似的；广义上来说，线段树分治是考虑外部对内部的贡献。 ~~也就是说，这和线段树没什么关系。~~ **$LOJ\ 121$ 动态图连通性** 就是$link,cut$，判断连通性三个操作。$n\le 5000,q\le 5\times 10^5$ 考虑进行线段树分治，显然每条边的存在区间是可以弄出来的，最后没被$cut$的边就一直到$q$。 我们对每个线段树上的节点都开一个$vector$，把每个存在区间都存到至多$\log$个$vector$，这样空间复杂度是$O(q\log q)$。 在询问时我们对线段树$dfs$，利用一个不带路径压缩的启发式合并$dsu$，每次$dfs$到一个区间就$merge$两个点并把更新的部分压入$stack$，然后$dfs$回溯的时候就把它撤销。 实现上我们可以这么写： ```cpp void merge(int x,int y) { if(x==y)return; if(dep[x]<dep[y])swap(x,y); fa[y]=x; s[++tp]=pi(y,dep[x]==dep[y]); if(dep[x]==dep[y])++dep[x]; } int find(int x){return fa[x]^x?find(fa[x]):x;} void ruin(int x) {while(tp>x)dep[fa[s[tp].fi]]-=s[tp].se,fa[s[tp].fi]=s[tp].fi,--tp;} ``` 这样就可以直接减掉这次$merge$的贡献，无论是$siz,dep$都可以写了。 如果$dfs$到了叶子，我们可以看这个点是否有询问，有询问的话就查一下两个点。因为$dfs$的顺序实际上是按时间升序，所以可以直接用一个指针直接扫过去就可以了。时间复杂度是$O(q\log q+q\log q\log n)=O(q\log q\log n)$。 简单证明一下，栈内最多有$O(q\log q)$个节点，加上并查集的复杂度是$O(\log n)$，所以$push$的均摊代价是$O(\log n)$，总复杂度就是$O(q\log q\log n)$。~~这好像是个经典的势能分析~~ **$BZOJ\ 4025$ 二分图** 给定每一条边的存在区间，判断在某个时刻（实际上原题是一个$[x,x+1)$~~]~~的时间段但差不多）这个图是否是二分图。 好像有一个NOIP题（关押罪犯）有这么一个东西： 对于一条边把$(x,y'),(x',y)$合并，如果$(x,y)$在一个连通块就不合法了。 这个东西同样适用于二分图。如果$(x,y)$在一个连通块里，意味着这个图就不是二分图，因为$x,y$被某个反点固定在了二分图的一端，这个比较好理解。 实现和上道题几乎相同，但注意你合并的是$(find(x),find(y')),(find(x'),find(y))$。 **$[HAOI2017]$八纵八横** ``` 线段树分治傻题。 ——zsyzsy ``` 该篇博客因为不可预知的信息危害导致内容失踪。 ## $33.Cuboid\ Union$ 求长方体并的方法貌似不少，但$set+$扫描线的方法应该是最为方便的。 具体来说，如果你把一个点固定为原点建立三维直角坐标系，你可以发现，从后$(y)$往前，以$1$为长度单位把长方体切片的话，每一片的面积$(x,z)$应该是不断增加的，且应该呈一个锯齿状——即从左到右各个组成的矩形高度单调不增。 所以我们可以用一个$set<pair>$来维护当前切片的各个矩形的长和宽，因为是倒着插，所以实际上是一个添加的过程。 考虑当前切片比上一个切片增加的一个点$(x,y)$，它增加的面积应该是把一些锯齿合成一个锯齿。 我们可以利用$lower\_bound$找到第一个比它长的锯齿，为此应该添加$(neko,0),(0,neko)$两个边界。 然后从右往左$erase$，增加的面积除了第一块要特判一下，其他的都是原本的长乘上$\Delta$高。 直到下一个矩形的高已经不小于它了就可以$break+insert$了。在这其中已经更新好了答案。时间复杂度是$O(n\log n)$，因为组成锯齿的矩形数量最多$O(n)$个。 以上内容请**务必**画图理解。 ## $34.Tree\ Hash$ 这里介绍一种还算有效的有根树哈希方法。 首先$dfs$，把所有的$Hash[v]$拿出来排序。 然后$Hash[u]=siz[u]\sum_{i}Hash[v]p^i$。 但注意可能会出现小树同构的情况，就是两棵小树一样，计数题中可能会把两种同构情况算作一种方案，因此这里要注意一下。 为什么会在下面的上面呢，因为这原来是$53.$，因为计算几何太长了就和它替换了一下。 ## $35.Hash$ 是不是很意外我还不会$Hash$啊$qwq$ 一般来说，如果要匹配两个字符串中的子串，要把它们统计一下哈希前缀和和次幂的前缀和（就是你哈希乘的是多少）。 匹配的时候，用 ```cpp ht[r]-ht[l-1]*mpow[r-l+1] ``` 两个子串的这个东西是相等的话，那就是相等的。 ## $36.Fuka\ Ben/Fukua\ Beng$ $\huge\texttt{肥}_{\small\texttt{泵}^{\large\texttt{话}}}^{\large\texttt{克}_{\tiny\texttt{的}^{\small\texttt{说}}}}$ $\huge\texttt{一}_{\small\texttt{都}^{\large\texttt{不}}}^{\large\texttt{句}_{\small\texttt{信}\large\texttt{得}}}$ 1.搜索树上线段树合并 $Beng$哥非常热爱线段树合并。 2.“这个题有好多枝可以剪！” “这题有好多枝可以剪！”——oyiya “剪什么枝？这题直接容斥就可以了。”——Beng 然后发现了这题不剪枝复杂度是错的。 “$Faker\_Beng$啊，你怎么不剪枝啊？” ”$\cdots\cdots$这个题有好多枝可以剪！“ 3.“平衡树挺好的啊？” “$Beng$哥，我想把范围出高一点，但是出高一点要用$Splay\cdots\cdots$”——Shenwei “平衡树挺好的啊？” ——Beng 4.“（代码长度）小的就是大的，大的就是小的！” 5.“A是不可能让你A的。” “$Beng$哥，你看看$result$，这题有多少人A掉？”——Shenwei “$A$是不可能让你$A$的。”——Beng 6.“$10^7\times 500$怎么会爆(int)啊？！” “这题答案可能到多少啊？”——Shenwei “哎呀不会爆不会爆，$10^7\times 500,5e8$怎么会爆啊？！”——Beng 7.“NOIp2018之前的一些想法” 从前的我意气风发，现在的我迷茫无助。 停课让我安逸，让我觉得畏惧，甚至会出现一直颓废下去的恐怖想法，但必须要明白停课不是来搞颓的，而是真正的孤注一掷 。 了解我的人都知道我的高一有多么灰暗，在去年这个时候就一败涂地，甚至将要一蹶不振。但这或许是最后一次机会了，希望我能坚持到底。 以后我会把每天做了什么挂上来（向学 yyb 神犇学习！），以及每天考试挂分的原因放上来，及时总结方法，希望快点将状态调整过来，迎接挑战。 中秋之夜，还有$46$天，加油！ 希望各位能与我互相监督。分享我最近看的一本书中一句话与各位共勉！ ``` 长跑的目的不是更快，而是更强。 ------《强风吹拂》 ``` 8.僵硬$Fake$ “弱肉强食$\cdots\cdots$”——Shenwei “我好弱的。”——Beng “怎么说咧，无话可说。”——Shenwei “肖大佬强得无话可说。”——Beng 9.当$Faker$被问“你有没有$A$一道题”且他已经$A$时 “哎我都是抄（肖大佬）的。”/“大同小异大同小异。”——Beng 10.“你没改说明你不屑于改” “肖大佬你肯定改了这道题”（$fkb$指向一道$zzq\ slide$里的神仙题）——Beng “那要是我没改怎么办咧？”——Shenwei “你没改说明你不屑于改。”——Beng 11.云玩家的嘲讽 “$I\ Wanna$不随便玩。” 12 $Fake\ Beng$最爱的三样东西 线段树合并、后缀自动机、$bitset$。 “直接线段树合并”——Beng “哎别用$SA$，用$SAM$就可以了”——Beng “你就用$\_find\_first,\_find\_next$优化一下这个过程”——Beng 13.~~成独分子~~ （盯着成都市第七中学的$OIerDb$）原来成都和四川是一起算的名额啊！——Beng 14.传统艺能 $Faker\_Beng$热衷于$OIerDb$，并每天都要用它来$orz$机房的人和机房外的人。 15.对拍 拍一拍有助于身心健康。——Beng ## $37.Tournament$ 其实竞赛图的题我做得非常非常少。 $Landau's\ Theorem$ 兰道定理指的是， $$\sum_{i=1}^nd_i\ge\binom{i}{2}$$ $d_i$指的是出度从小到大的排序序列，且$i=n$时两边取等号。 证明其实比较简单，竞赛图的任意点集都满足$\sum_{i\in S}d_i\ge\binom{\vert S\vert}{2}$，这个比较显然，点集内的任意两个点都给予了1的贡献。 而且一个简单完全图的边数就是$\binom{n}{2}$，竞赛图的度数和也是如此，所以定理本身是比较简单的。考虑 $$\binom{n}{2}=\sum_{i=0}^{n-1}i\le n\times \max(a_i)$$ ，这也意味着当给定出度序列时，点个数的大小是$O(\max(a_i))$的，其实最大也就是$2\max(a_i)+1$，简单地推一下就好了。 依靠这个，我们可以作出限制，进行操作。 ## $38.Derangement$ 之所以要写这一篇主要是因为$zhou888$太神了，加上$Beng$哥博客又写得不清不楚，于是就开一下坑。 经典的错排问题指的是求有多少个排列$\{p_i\}$满足$\forall i,p_i\neq i$。我们稍微将它扩展一下，就是存在一个排列$\{s_i\}$，求有多少个排列满足$\forall i,p_i\neq s_i$。 ### 1.$O(n)$递推 很经典的式子。 $$f[n]=(n-1)(f[n-2]+f[n-1])$$ 考虑一下这个式子的意义，我们新填一个数$x$，首先这个数不会填到被限制的位置，然后被占了位置的那个数（**这个数指的是被限制不能填$x$填的那个位置的对应的数$y$，下文中用$lim[x]$表示x不能填到$lim[x]$这个位置**）如果填到限制自己的位置，那么其它数就可以直接错排，这样的方案数就是$f[n-2]$；否则你可以理解成使$lim[y]=lim[x]$，然后$n-1$个数继续错排，方案数是$f[n-1]$。 ### 2.$O(n)$容斥 这个相对来说倒是更好理解。 $$ans=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=\sum_{i=0}^n(-1)^i\frac{n!}{i!}$$ 简单来说，我们枚举有哪些位置的数必须放在原位，其它位置随便乱排。 应该可以感性理解这个东西~~，所以我们就当它是对的~~。关于它与$1.$中递推式的等价证明，可以使用数学归纳法。不知道有没有更好的证明方法。因博主比较懒且正在文化课期间（也正是因复习到了错排才来更新一下新的理解），暂不赘述。 ### 3.继续扩展 我们考虑这样一个问题：其中的$k$个数可以不满足限制。 我们可以用一个$O(nk)$的$DP$解决问题。 令$dp[i][j]$表示填了前$i$个数，其中有$j$个数可以不满足限制的方案数。 首先$j=0$的情况和错排一模一样，直接转移： $$dp[i][0]=(i-1)(dp[i-2][0]+dp[i-1][0])$$ 然后我们考虑$j>0$的情况： $$dp[i][j]=dp[i-1][j-1]+dp[i][j-1]$$ 这个式子怎么理解呢？ 首先$dp[i-1][j-1]$比较好理解，就是这个数$x$就填在$lim[x]$上，那就是其它的$i-1$个数去排；如果这个数不填在那个位置，不就相当于这$i$个数只有$j-1$个可以不满足限制的数了？那就是那一部分排列的方案数，加起来就可以了。 ### 4.变得更快 ~~这部分是用来应付毒瘤出题人的。~~ 注意到，如果把$i,j$交换，那么这个$j>0$的转移是与组合数的递推一模一样的形式。 那么我们只要$O(n)$处理出$j=0$的情况，也就是这个奇怪的转了一下的杨辉三角的第一行，大概就可以用一个组合数直接算出答案了。~~因为没有实现很虚啊不知道怎么写~~ 不过这总结也差不多了吧，或许也有更优秀的实现方式$(O(1)?)$，欢迎联系我这小蒟蒻x ~~【话说感觉现在写总结越来越长越来越喜欢分阶段了啊~~