ybjnb

摘要： 平衡树 二叉搜索树 性质：一个节点 \(x\) 的左子树的关键字都比 \(x\) 的关键字小，右子树的关键字都比 \(x\) 的关键字大。 这种结构规定了左边都比右边小的关系，所以可以很方便的寻找第 \(k\) 小，或者叫询问小于 \(k\) 的元素个数。 treap "树堆" : Tree + H 阅读全文

摘要： 小数论 若无特殊说明 \((x, y) = gcd(x, y), d = (x, y), [x, y] = lcm(x, y)\) 唯一分解定理 \(x = p_1^{α_1} \times p_2^{α_2} \times ... \times p_k^{α_k}\) 一个数的约数个数 约数个数 阅读全文

摘要： 接dfs序。 https://chuna2.787528.xyz/ybjnb/p/19089551 树剖 （dfs序的性质依旧满足 即子树也是一段连续区间） 将一颗树转化为一个序列 将树上任意一条路径转化成 log(n) 段连续区间 然后就可以用序列数据结构维护信息。 对于u节点 他有子树y1, y2, 阅读全文

摘要： 简单的根号相关问题 (根号分治 定期重构 分块 莫队) 一. 根号分治 精髓就是拼接两个暴力 1. 余数根号分治：Remainder Problem 首先直接单点更新O(1)，查询暴力跳O(n)。这个暴力的有点在于当查询的x比较大的时候，那么跳的次数就比较少。 另一种暴力思路就是维护c[i][j]为 阅读全文

摘要： 一.首先定义看定义 树是N个点N-1条边的联通图 基环树是N个点N条边的连通图 不保证联通就都是森林 所以基环树就是在树上加了一条边，使得树上有了一个环 基环树的常见处理方法 把环上的一条边单独处理， 这样其余部分依然是一棵树 把环单独处理， （缩成一个点）这样其余部分依然是一棵树 二、内向树和外向 阅读全文

摘要： 差分，LCA 运输计划 比较简单的题，9.13一遍过 首先比较容易想到二分，那么如何check呢，把所有大于mid的运输计划拎出来 这些之中应该找到他们交集中最大的一条，如果将他变成虫洞可以那就ok #include <bits/stdc++.h> #define rep(i, a, b) for( 阅读全文

摘要： 动态开点线段树 当权值线段树的值域很大时， 通常有两种解决方法 离散化或者是动态开点 理解性记下 query 没点的时候直接返回 区间修改最多开2logV个节点 单点修改最多开logV个节点 首先开一个root, tot表示根和节点个数 对于一次访问 若不存在此节点那么新开一个节点 (注意引用符号是 阅读全文

摘要： 调试DP:把他们都打印出来，脑袋清醒地想初始值和转移条件(边界) 简单优化 先写出朴素做法再思考优化 关于绝对值， 我们要考虑拆掉绝对值来做 T1 你要构造一个长度为N的数列，数列的元素在1和M之间，如果数列相邻两个数变化比较小，你会感到无聊，所以你希望相邻两个数的差不小于K。 求满足要求的方案数 阅读全文

摘要： 接上一篇DP DP的本质就是 化零为整, 化整为零 : 把一堆方案按照一定因素划分成为较少类数的方案, 同一类方案有共同特点使得可以一起转移, 一般来说同一类方案我们记录的是最优的那个 状态的转移则是化整为零, 考虑当前状态从何而来, 分类讨论 DP的状态设计是难点, 只要设计出状态并且确保他是对的 阅读全文

摘要： 1.统计每个点入队次数，如果某个点入队n次说明有环(bellman-ford) 2.统计当前每个点的最短路中所包含的边数，如果某点最短路所包含的边数>=n，则有负环（常用） 有很多块怎么解决: 把所有点都放入队列,距离初始化为0 阅读全文