xixike

主席树的最基础的操作就是查询历史版本区间第 kkk 大，带修。 这个问题的基础解决思路：对于每次修改都建一棵权值线段树，显然空间开不下。 这时可持久化线段树的思路就应运而生了。 主要思想： 不难发现，每次修改只会有一条链上的值发生改变，所以我们不需要建出整棵新树，只需要把新建那条链上的点即可。 所以空间就是 nlog⁡nn\log nnlogn 的。 我们还要在权值线段树上做个前缀和来方便查询，每次查询时，就是在权值线段树上二分的过程。 注意到我们要建的是权值线段树，所以要对输入的值做一个离散化。 不多说了，直接贴代码吧。 code:code:code: mark#include...

# 点双，边双 （掌握较为熟练） # 点双： 定义：删去一个点之后，图仍然联通，则称这个图是点双联通的。一个无向图里最大的点双联通子图称为点双连通分量。 算法：跑 Tarjan，回溯过程中若 lowy≥dfnxlow_y \geq dfn_xlowy​≥dfnx​ 就出栈直到目标节点出栈，弹出的点为一个点双。 # 边双： 定义：类似于点双，只不过条件都改为边。 算法：同样和点双很像，如果有 lowy>dfnxlow_y > dfn_xlowy​>dfnx​ 那么存在点双，弹栈加点即可。 # kmp & AC...

# UVA1292 Strategic game 树形 dp\text{dp}dp 板子题。 直接设 fx,0/1f_{x, 0/1}fx,0/1​ 表示 xxx 子树内所有的边都被看守到，且 xxx 不放 或者 放 士兵的最少士兵数。 xxx 如果不放士兵，它的所有儿子节点都必须放士兵，即： dpx,0+=dpy,1dp_{x, 0} += dp_{y, 1} dpx,0​+=dpy,1​ xxx 如果放士兵，那么它的儿子可放可不放，即： dpx,1+=min⁡{dpy,0,dpy,1}dp_{x, 1} += \min\{dp_{y, 0}, dp_{y, 1}...

早就想搭一个自己的博客了，然而本人水平有限，一直没有弄好 QwQ。最近到二南集训，在 yyt 神仙的帮助下耗时一晚上搭建完毕（主要是用了个假的梯子）。 在此感谢 yyt 神仙的大力帮助，以及 rbs 神仙两秒钟搞定 markdownmarkdownmarkdown 渲染问题，baoshuo yyds! 这个博客会不定期更新 OI 相关内容，以及游记等。 之前的博客就不往这里放了，想看更多请到 xixike-cnblogs

# P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT/FWT) 先放一个模板后面写题直接复制就可以了。 FWTFWTFWT 原理就不解释了，大家自己去看题解吧 QwQ 这里直接放代码。 CodeCodeCode #include <bits/stdc++.h>#define ll long longusing namespace std;namespace IO{ inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch =...