悠然w

线段树

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章 / 线段树（共4篇）

loj #2179. 「BJOI2017」树的难题点分治+线段树

对于树上统计路径的问题我们通常要用到点分治来搞一搞。首先我们点分治。摄当前的分治中心是 x,那么把 x 周围的点按照颜色排个序。统计的时候我们建两颗线段树，设当前处理到的 x 周围的点是 y，x 和 y 之间的点的颜色是 z ，那么第一棵线段树是 z 之前的颜色(不包括z)，第二棵线段树...

2020-07-24

0 0

关于线段树的一些认识

线段树学得好，能维护超级多的东西。 \(CSP\) 和省选都会用到，建议早点学会线段树就是将一些区间整体的操作摞到了一块上，精华还是在lazy标记上。以区间加为例想要对一部分加上某个数，很明显可以先不暴力加上去，而是打上一个标记，代表从 \(l\) 到 \(r\) 都要加上某个数当...

2020-06-14

0 0

洛谷 P3997 [SHOI2013]扇形面积并线段树

考虑每个小区间的的贡献，显然是只用到了覆盖了这个小区间的值里面第 \(k\) 大。倘若我们已经知道了覆盖当前区间的值都有多少个，我们就可以在线段树上二分找第 \(k\)大。现在我们并不知道，我们可以用差分+线段树上修改的方法来完成对当前值的出现次数的维护。 #include<al...

2020-04-08

0 0

[武汉加油] bzoj 1135: [POI2009]Lyz

忽略数据范围，我们就可以用二分图搞一搞，但事实证明我们并不能忽略(滑稽) Hall定理：对于一个二分图，设左边有个n点，右边有个m点，则左边个点能完全匹配的充要条件是：对于1<=i<=n,左面任意i个点，都至少有i个右面的点与它相连。换成人话就是这样的：设\(a_i\)为...

2020-02-16

0 0