玄学算法/精彩DS总结 Laku

## $6.5.Segment\ Trees$ 线段树相关的内容非常多，这是一个导航。 $I,3.$主席树$,6.$线段树合并 $Laku,7.$考场上的线段树 $Vasuku,32.$线段树分治 $Vazuku,41.$线段树优化建边 ## $7.Segment\ Tree\ in\rm\ Test$ 考场上的线段树和平时的线段树不同，有很多地方容易写错。 0. **观察题目的需求，如果某些信息是不需要维护的，将它们缩略后发现可以变成区间修改或区间查询的形式，可以考虑使用线段树进行维护**（比如某些题只需要维护偏序关系而不是准确数值，可以把它们变成01）。 1. 注意存储信息的下标一般都与$\rm root$有关。如果不是，说明写错了；注意是$tagl\le l,tagr\ge r$。 2. 注意进行某些信息的删除时，许多相关信息都要清零。**如[HNOI2017]单旋这题，我调了很久的一个错误就是在删除节点时父亲忘清零了。~~还导致我搞了150行，真是不符合我以往的压行风格~~** 3. 注意信息合并的方式。如线段树优化DP，转移的部分要记清。**还有$\rm pushup$操作的直接覆盖，不能重复增加。** 4. 每个地方的$\rm pushup$和$\rm pushdown$不能漏掉。树剖转到线段树上记得加上$\rm w(dfn)$。 ## $8.Others$ ~~正在整理中。~~整理完成。分成了四部分。 ### 思维扩展 **一道题的复杂度/DP/贪心/维护方向往小的那个数值想。** **考场上会出现这样一种情况：做DS题细节多/卡常，然后陷入了一种过热BUFF的状态。这种时候要保持冷静，合理利用BUFF，必要时可以去外面走一发。如果很难调出来，应该先计算调完还需要多久，再决定是否继续。** **写正解顺序：脑补细节->开始写->过样例->眼查代码，此时脑中就要有这一步要干什么，注意有可能写错的细节->写bf->拍->造极限gen，特殊gen（->卡常）->再拍->眼查代码，要求同上。务必不能只拍不管。** 当贪心题没有明显的贪心策略或者贪心策略比较麻烦的时候，考虑枚举一个方面，说不定答案可以快速算出。 看见离线区间询问想差分。 构造题应当充分利用全部的条件，直接从整体上考虑问题，一般是一个很规整的通解；如果想想得清楚一点，可以考虑把条件列成式子。 请注意如果一个结论不好做，考虑变化这个结论，尽量规约成简单的形式。 整体与一致是分不开的，如果题目要“一致”，那么可以进行“整体”。例如$AGC004E$。 对于一类不取全部序列的划分问题，在$DP$的时候我们不一定需要枚举断点，也可以设$[0][1]$表示不在划分中和处在划分中。 当~~想破脑袋~~没有想到贪心策略的时候，或许暴力$DP$是一个不错的选择。 当一个性质不好做题的时候，考虑在这个性质的基础上推下一个性质，这个新性质应该是对原性质的一个总结/转换。 当题目给定的是四相邻建边图的时候，注意这可能是个**二分图**，因为它只有偶环。 **如果你看出了某个性质，尝试将它数值化，这样或许可以使用数据结构维护。** 有的$DP$可能暗含构造方案，因此某些寻求最优问题可能可以通过状态设计来解决。 **遇到有关斐波那契的题，可以先推一下性质。** 如果一道题只适合维护数量信息而不是维护最值信息（如第$k$大，最大最小值），可以考虑二分答案转化为判定性问题。 如果没有明显的逐步贪心策略，可以考虑终态如何，然后列式子寻找最优解。 **注意题目没有说在线那就先看看离线** ### 经典套路 **$out[x]>dfn[y]$表示y在x子树内；主席树之类$dfn$处+ $out$处-可以方便单点修改统计链上答案。** 一类$DP$计算最大最小值方案数时，可以将所有数排序之后按顺序填，方便算方案数。 期望题需注意，最低档暴力可能是没有必要的，因为期望可加性/线性性或许可以直接算贡献。 树随机=树高期望$\Theta(log)$ $two-pointer$在单调性计数时十分适用。 用堆维护前$k$小值的套路：一个大根堆维护前$k$小值，一个小根堆维护其它数，每次更新时，从小根堆堆顶$push$进大根堆，再把大根堆堆顶$push$进小根堆。只要大根堆堆顶大于小根堆堆顶就一直更新。 与质因数相关的一些Trick： 1. 质因数个数为$O(\log)$的； 2. 普通分解质因数的复杂度是$O(\frac{\sqrt{n}}{\ln \sqrt{n}})$。 所以如果你要把一个数分解成一堆质数才能做的话，不要质疑你的复杂度会错。 如果$max$找不到，尝试转化为找$min$。比如一个环，找最远的某个性质的点找不到，可以找$\frac{n}{2}$外那个点的最近点。 **当询问为区间时，不要简单地认为这就是对的，要找最近区间前面和后面，因为会有这个最近区间某一方向非常长然后比它前面/后面那个区间更靠近那个点了。** **遇到中位数/某个位置的数想二分**$0,1/1,-1$。 有一个黑白染色/01串中很常见的套路：如果它要求把一种类型的颜色区间翻转：那么可以转化成01移动等各种对两种元素操作的形式：如01或10翻转成10或01，可以理解成1向左走和1向右走。如此转化模型能优化解题。 $dp$题什么东西最难求，可以考虑把它设到状态里。 考虑计数题行列同时有限制的时候，可以考虑对一维进行容斥/斯特林反演，然后另一维就可以在推式子的时候默认满足限制，就可以把限制去掉，就比较好计数了。例子可以看10.7dyy的题。 限制转移时与当前元素无关的时候，可以考虑以没有这个限制的方式进行方便地转移，再利用容斥等去掉这个限制。 当暴力/$l=1,r=n$等特殊询问有一些性质的时候，考虑进行分块。 数据结构题方便维护的是不变量，比如全体移动就可以变为动态开点+线段树二分。 单调栈的维护方式是**如果栈顶满足某个偏序关系则一定比当前枚举的元素劣，因此才能弹掉栈顶。** 构造类计数题直接考虑最终构造的序列或是什么东西的性质，往往比考虑怎么构造这个东西来计数更方便。 注意有时候分类讨论然后计算的题说不定可以通过转换原数组来方便代码。 计算两个点集$S,T$相连的边可以用$edge[S|T]-edge[S]-edge[T]$。看起来没什么用，但是当你要计算连接$S,T$两个点集的概率的话，$\frac{prob[S|T]}{prob[S]\times prob[T]}$是不错的选择。 考虑计数$DP$的两种转移方式，一种是把之前的个数保存，在当前转移计算数量，一种是预支之后的个数，先计算完数量并转移。 当你需要在数点时记录下标的时候，可以用$set$去维护。 求区间并可以直接差分+前缀和，非常方便。 一个$dp$如果正着反着都可以$DP$，而且式子还很类似却可以不消掉，将两个式子结合可以得到新的式子，并且这个式子说不定可以直接求出最终的答案例子可以参考$2019.4.2\ T3$。 ### 细节注意 **对于dfs来说，某些仅在当前状态使用的有初始值的变量最好定义局部变量防止不必要的错误。** 手写宏定义chkmin/max里不要放变量更改，因为会更改多次。 scanf等内部最好不要增减变量。 主席树注意**不要**判$if(!root)$，而且当前点挂了多个询问一定要先继承父亲的根，然后一个一个更新($update(rt[u],rt[u],\cdots)$，第二个带取地址) 割点记得判根，以及去重或者直接用$map$。 **ST表相关数组（如log）一定要开到两倍（与steko等同）！qwq** 注意FFT是 ```cpp for(n=1;n<=m;n<<=1)++cnt;--cnt; ``` 而不是$n<m$，因为如果$m$是$2$的次幂比如$16$它应该是$10000$有$5$位，$cnt$是$4$而不是$3$，$n$应该是它的两倍（也就是多一位）这样$1\to n-1$才是正确的。 **注意$0^0=1$，而如果用递推的方式求$0$的次幂还是倒序，那么这个要特判。** 对于所有$if$的边界情况（**尤其是回答询问时**）要务必细心检查。 注意预处理部分如果要从正解复制到暴力中的话请务必**重新检查**。 ### 易错理解 **点分治过程中的父亲和原树父亲没有任何关系！有可能你是从儿子dfs上来的，所以除了题目让你统计原树结构上的数据，否则一律统计分治结构上的数据，也就是说当前父亲你要直接放到dfs里。** **luogu的Miller-Rabin模板代码是错的所以请去loj。** 拓扑排序在非$DAG$时不一定是错误的：当你的$DP$有第二维时，你的$DP$可以重复进行拓扑，也就意味着你会把上一次环的贡献在更新时给推过去；而只要你最后一次所有环的$dp$值不再有贡献的话，你就能够把答案推过去的话，那答案就正确了。可以参考$[NOIP2017]$逛公园。 一类带选择和分类讨论情况的复杂DP，前面的某些选择具体是什么可能是有后面的转移来决定的。比如说线性基计数可能前面的向量只有第一位是之前的转移中确定的，它的之后的位（低位，比如说当前位）具体是什么应该由当前的转移决定。 **千万不要一开始就直接想反面或侧面计数！应该先想正向计数的限制，再考虑其它问题，否则很容易想复杂。参见HNOI2018D1T3的时候。** ### 原来写的快没用的 Dinic注意反向边加流量 AC自动机注意入队 SPFA注意是dis[v]>dis[u]+e[i].w 网络流注意初始边标号t=1 ## $9.Entirely\ Dichotomy$ ### ~~究竟是谁说整体二分像CDQ分治的？？？~~ 做AGC002D的时候顺带了解了一下这东西，于是终于又填一坑。 整体二分是建立在二分答案的基础上的。如果答案满足单调性，它可以把所有的询问挂在区间$[l,r]$中，对$mid$进行check，将满足条件的询问放到$[l,mid]$中，不满足的放到$[mid+1,r]$里。 整体二分需要满足对于一次$check$是$O(\log)$以下的，不然复杂度是保证不了的。 具体实现来说，我们将一个三元组$(l,r,vec)$搞成一个结构体，第三个是个$vector$存包含在里面的询问。 这样可以很方便地用一个队列来进行处理，每次取出$[l,r]$，然后$push\ [l,mid],[mid+1,r]$所对应的三元组进去。当$l==r$时，就可以确定这个询问的答案了。总时间复杂度$O(n\log n)$。 还有一种递归写法，这样能方便限制区间的范围，可以方便地对一个整体数据结构进行撤销或者是什么。 $\rm [AGC002D]\ Stamp\ Rally$ 给定一个无向连通图和$q$个询问，每个询问给定$x_i,y_i,p_i$，表示A从$x_i$，B从$y_i$开始，必须经过$p_i$个点。使经过下标最大的边最小。 **我发现这题整体二分并没有难到我，反而最基础的对于一个询问如何判定答案让我卡住了，所以基础非常重要。** 考虑对于一个询问，我们二分答案，然后用并查集维护能到达的点数量。当当前并查集内包含的边$>mid$，我们就要暴力重构并查集。 这样总共的复杂度是$O(qn\alpha\log m)$的。 考虑利用整体二分解决，对于一堆询问都可以$O(1)check$。 此后$dyx\_diversion$的写法是利用递归解决，利用不路径压缩的并查集可以撤销，这样撤销的边的总和肯定不会超过$O(m\log m)$。 ~~这样的复杂度看起来很对，我的复杂度看起来很错。~~ 我们怎么证明暴力重构的复杂度也是正确的呢？~~我现在好像证明不了。感觉势能是$O(m^2)$级别的啊~~ ~~但我的确跑得比他还快啊~~ ## $10.Monotonicity\ of\ Decision\ Making$ ### 文档再次更新：这玩意在单层的复杂度是$O(n^2\log n)$的，多层/转移的复杂度也是$O(n^2\log n)$的。~~所以单层的时候复杂度就是错的还没有暴力优秀尽管跑不满~~当然，单层且DP与前面的DP值无关的时候复杂度也是正确的。~~但这能叫DP嘛~~ ### 文档更新：这篇文档记录的是一个并不具有很大作用的东西，仅仅能作为一个替代品。以下内容包含夸张而并没有那么大意义的内容，并且因为作者本人希望把它留下来而没有改变格式，请酌情观看。~~并不保证作者本人撰写时未受到有害模因的影响。~~ $$ $$ ### 决策单调性是一个非常玄学的东西，广泛应用于单调队列/栈/斜率优化中。也只有当$\rm i>j\&f[i]>\vert <f[j]$时，这些DP优化才能够使用。其中单调队列/栈遇到$\rm s[i]\times f[j]$直接GG，斜率优化则难度更高。 在一次偶然中，我发现了一种神奇的分治方法~~（暂且命名为$\rm ClarisDC$，因为据博主说这是$Claris$在一场CF里打出的代码~~为了避免一些麻烦的问题叫它双区间分治好了，如果按我的命名方式那就是$\rm L-Sections\ DC$），这种方法可以以$\Theta(nlogn)$换$\Theta(n)$的代价，换取代码的简单和思维的简化。~~好像某些题解中有写到基于单调栈的动态维护决策区间的分治，貌似和这个比较像，不过这个好像没用到单调栈~~ 我们来看一看这种方法的要求： 假设$i>j$时$f[i]>f[j]$。设从$x$转移到$i$、$y$转移到$j$是最优的状态。如果可以发现$x>y$，我们考虑一种分治： ```cpp void dc(int l,int r,int dl,int dr) { //复杂度错误的单层 //[l,r]表示现在更新[l,r]区间dp[mid]的最优值 //用j表示j是更新f(i)最优值的最优点 //那么[dl,dr]表示更新dp([l,r])的点，一定在[dl,dr]范围内 int mid=(l+r)>>1,dm=dl； if(l<mid)dc(l,mid-1,dl,mid-1); //由于当前决策的左区间的dp值一定要先求出来，所以先往前分治，决策区间可以直接改成mid-1 //更新[l,mid-1]的最优点，一定在[dl,dm]范围内，然而dm并没有求出来 int now,dx=aworstvalue; f(i,dl,dr) { if(i>=mid)break; now=f(i,mid);//从i转移到mid if(now>dx)dx=now,dm=i;//记录最优点 } dp[mid]=dx;//更新dp[mid]的值 //更新[mid+1,r]的最优点，一定在[dm,dr]范围内 if(mid<r)dc(mid+1,r,dm,dr); } ``` ```cpp void dc(int l,int r,int dl,int dr) { //复杂度正确的多层 //[l,r]表示现在更新[l,r]区间dp[mid]的最优值 //用j表示j是更新f(i)最优值的最优点 //那么[dl,dr]表示更新dp([l,r])的点，一定在[dl,dr]范围内 int mid=(l+r)>>1,dm=dl； //更新[l,mid-1]的最优点，一定在[dl,dm]范围内，然而dm并没有求出来 int now,dx=aworstvalue; f(i,dl,dr) { if(i>=mid)break; now=f(i,mid);//从i转移到mid if(now>dx)dx=now,dm=i;//记录最优点 } dp[mid]=dx;//更新dp[mid]的值 //更新[mid+1,r]的最优点，一定在[dm,dr]范围内 if(l<mid)dc(l,mid-1,dl,dm); //由于当前决策的左区间的dp值在之前求出来了，所以可以这样分治 if(mid<r)dc(mid+1,r,dm,dr); } ``` $($搬运自$\rm MathonL$的博客并做了修正$)$ 可以发现，只要上文叙述的性质满足，那么这样的分治就是正确的。 复杂度证明的话，一个区间至少也要分成两个相等的区间，也就是最多分成$O(\log)$个相同区间，复杂度就是正确的。 ## ~~$\sout{Claris}$太劲了！！！！~~ $P.S.$ 如果题目不满足这个性质，但又差不多满足这个性质，往右边分治的决策左区间改成$\rm chkmax(dl,dm-s)$,$\rm s$随便调一个比较小的值(如$100$)就可以骗分了：大多数情况下决策最优位置还是很近的。 ### $P.S.S.$ 如果题目不满足这个性质，但又差不多满足这个性质，对于最后一个点，我们同样可以加一个特判： ```cpp int las=aworstvalue; f(j,1,n-1)las=f(j,n); dp[n]=las; ``` ### 这样可以避免最后一个点的决策最优点非常早的问题。可以给$\log(n)$个这样的节点都加上这个特判。 ### 还有一点就是，其实分治中的$dx$不一定需要重置成最劣值，因为你的分治实际上是从左往右的，不满足的话也正好可以应对一些决策反而更劣的情况。注意：这种方法不一定正确。 ### 对于$dx$还有一个地方：你的$dx$一定要尽量劣，比如dp数组初始化为$\infty$，你就得是$2\times\infty$甚至更高，这样才能保证决策区间的缩小。 对于上面的乱搞，可以参考$\rm [NOI2007]$货币兑换、$\rm [HNOI2010]$玩具装箱、$\rm [APIO2010]$特别行动队、$\rm [SDOI2016]$征途。 ## $11.CDQ\ Conquering$ $CDQ$分治有两种：第一是先处理左右区间的情况，然后合并结果计算答案； 第二是先处理左区间，之后计算左区间对右区间的贡献，再处理右区间。 两种的区别就是：第一种主要是在你必须处理完子区间的情况再合并，第二种主要是你必须要处理好左区间的贡献再去看右区间，比如$12$中的那种情况。 实际上是一种降维的思想，将一个高级维度平视成可以一起解决的低级维度。 ## $12.Slope\ Optimization$ ### 数： $\rm[HNOI2008]$玩具装箱 $$dp[i]=\min(dp[j]+(sum[i]-sum[j]+(i-(j+1))-l))^2$$ $$=\min(dp[j]+((sum[i]+i)-(sum[j]+j+1+l))^2$$ $$=\min(dp[j]+a[i]^2+b[j]^2-2a[i]\times b[j])$$ $$=\min(dp[j]+b[j]^2-2a[i]\times b[j])+a[i]^2$$ 若$j<k$且$k$比$j$优，则 $$dp[j]+b[j]^2-2a[i]\times b[j]>dp[k]+b[k]^2-2a[i]\times b[k]$$ $$2\times a[i]\times(b[k]-b[j])>dp[k]+b[k]^2-dp[j]-b[j]^2$$ $$a[i]>\frac{dp[k]+b[k]^2-dp[j]-b[j]^2}{2(b[k]-b[j])}$$ 定义一个点$(b[j],dp[j]+b[j]^2)$，则$slope_{j\to k}$小于$a[i]$。 $$\frac{dp[r]+b[r]^2-dp[r-1]-b[r-1]^2}{2(b[r]-b[r-1])}>\frac{dp[i]+b[i]^2-dp[r]-b[r]^2}{2(b[i]-b[r])}$$ 这里有一个不被卡精度的小技巧：把斜率转化为十字交叉的形式，即这么写： ```cpp struct node {ll x,y;}; node check(int l,int r) { ll x=2*(b[r]-b[l]),y=dp[r]+b[r]*b[r]-dp[l]-b[l]*b[l]; return (node){x,y}; } bool calc(int l1,int r1,int l2,int r2) { node p1=check(l1,r1),p2=check(l2,r2); if(p1.y*p2.x>=p2.y*p1.x)return 1; else return 0; } ``` $check$判头，$calc$判尾。注意$x$要乘$a_i$。 ~~务必注意使用这种方法时有关$\rm long\ long$的问题~~ ### 形： 这个就指的是，把一个$DP$方程中的两个定值而且是之前的值$(j)$分别当做$x,y$，哪个与$i$有关哪个就是$x$。 然后我们让$dp[i]$作为截距，问题转化为求截距最值。 这样的话，同纵坐标的情况下显然有一边更优，但纵坐标变化，直线也有变化，可能会出现新的更优解，于是就形成了一个凸壳。 $\rm[HNOI2008]$玩具装箱 $$dp[i]=dp[j]+b[j]^2-2a[i]\times b[j]$$ $$b[j]^2-2a[i]\times b[j]=dp[i]-dp[j]$$ $$b[j]^2+dp[j]=a[i]\times 2b[j]+dp[i]$$ $$y=kx+b$$ $\rm[NOI2007]$货币兑换 $$dp[i]=\mathrm{max}(dp[i-1],maxb[j]\times b[i]+maxb[j]\times rat[j]\times a[i]),$$ $$maxb[i]=dp[i]/(rat[i]\times a[i]+b[i])$$ $$-\frac{b[i]\times maxb[j]+dp[i]}{a[i]}=maxb[j]\times rat[j]$$ $$kx+b=y$$ 其中$-\frac{b[i]}{a[i]}$是斜率，$\frac{dp[i]}{a[i]}$是截距。我们要求的是截距尽量大。 既然都不单调，使用$CDQ$分治。 一开始按斜率排好序，开始分治。 分治首先将下标小的放左边，处理完左边的，维护左边的凸壳（此时左边已经按$x$排好序），此时左边$x$单调，右边斜率单调。直接建单调队列，更新右边的答案。 更新结束之后处理右边，之后将整个区间按$x$排序，当前分治结束。 以上全部是垃圾玩意儿。 除了最裸的东西单调队列有点用（$O(n)$）之外，其它的不单调情况完全可以用李超线段树代替，还是$O(n\log n)$的。 我们现在知道 $$dp[x]=\max_y(coefa[y]a[x]+coefb[y]b[x])$$ 那为了化成$y=kx+b$的形式，我们让整个式子$\div coefb[y]$ $$\frac{dp[x]}{b[x]}=\max_y{coefa[y]\frac{a[x]}{b[x]}+coefb[y]}$$ 可以发现右边变成了$kx+b$的形式。 我们考虑一种非常优秀的替代方式，并且不需要任何限制条件。 显然我们要求$dp[x]$的最大值，也就是$x=a[x]$（注意两个$x$的有意义不同）的最优直线。这个东西显然能很方便地使用李超线段树直接维护，每次直接查就可以了。