软件工程专业在读，，收到了老师的作业 qwq 第一次碰算法题以外的东西，，有点有趣诶 (๑Ő௰Ő๑) 就是让做一个这种菜单： <img src="https://s1.ax1x.com/2020/10/15/0TO3kT.png" width="500px"> 敲一下回车是这样子： <img src = "https://s1.ax1x.com/2020/10/15/0TXTVx.png" width =...

嗯。。传说中的主席树，迈出了可持久化的第一步 |･ω･｀) 万恶之源： P3919 【模板】可持久化线段树 1（可持久化数组） ​ 显然，每次修改都开一颗线段树，空间 n2n^2n2 爆炸。。 ​ 但因为是单点修改，所以对于每次修改操作，直接开一条链就好了， nlog⁡nn \log nnlogn 大小。 ​ 用 root [i] 记录每次操作的树根即可，， 具体长这样： <img src = "https://s1.ax1x.com/2020/08/16/dExadS.jpg" width =...

线段树，yyds！ —— 沃・兹基硕德 # 重链剖分 预处理：两遍 dfs，第一次处理 子树大小 sz， 深度 dep， 父节点 fa， 重儿子 son； 第二次处理 重链顶点 top， 新编号 dfn， 新编号对应原节点 rev。 修改 / 查询： 两点不在同一条重链上：深的往上跳至 fa[top[x]] ，不断重复。 直到两点在同一条重链上：此时两点编号连续，直接处理即可。 整颗子树：整颗子树编号连续，即在 [dfn[root], dfn[root] + sz[root] - 1] 区间内。 # 线段树 ​ 满足区间加法的东西都可以用线段树维护欸嘿嘿 (´▽｀)...

# Prim 半年前，计划里有那么一道题，直到退役都懒得去做.. P1265 公路修建 裸题写半个下午咱真是菜得不行了 TAT（辣鸡 dev 又卡我。。懵逼了半小时，重启，解决问题（｀Δ´）！ # 一句话口胡 prim 流程 ​ 先把随便一个点放入联通块，每次贪心找 离当前连通块最近的点 并将其加入连通块，再用该点更新 连通块外的点 与 当前连通块 的最小距离，把所有点加入为止。 这题就算 prim 的板子叭.. code: void prim(){ memset(dis, 0x7f, sizeof(dis)); //dis 记录每个点到当前连通块的最小距离 dis[1]...

DATE: 2020-08-07 退役老 OIer，，在搞 ACM 但不敢自称 ACMer 的菜菜，， 高中毕业，算法相关的纸质笔记全被麻麻按斤卖了，嘤～ 为防止悲剧再次发生，咱决定在这里丢笔记 qwq lazy and vegetable，写文章随缘呗。。_(:з」∠)_ 反正不会有人看的，反正不会有人看的，反正不会有人看的... DATE: 2020-12-20 呜呜呜原来的博客乱成一团了 QAQ 毕竟还是萌新不太会操作，， 还是推倒重来叭。。 DATE: 2021-01-19 自动部署太爽了哈哈哈哈～～