搜索结果
查询Tags标签： 线段，共有 135条记录-
线段树上状压（位运算）
洛谷P1558 分析： 颜色类型只有 \(30\) 种,可以利用二进制进行状压。 线段树维护一个二进制数表示区间的颜色为哪一种，将这个区间的颜色进行状压，每一种颜色对应二进制数的某一位。合并区间时将两个子节点的数按位或即可，题目区间修改为直接覆盖，统计答案时只需统计对…
2022/9/8 23:56:10 人评论 次浏览 -
可持久化线段树
现想现写的，没有借鉴别人的任何东西。 可持久化线段树1 考虑不会变得太多，每次该值操作只会改变一个位置的值，其它位置是可以继承的。如果用数组，那就是下标继承。如果把数组分成 \(2\) 半，那改一个值，就一半继承，另一半重新赋值。而用线段树，就可以做到区间继承 …
2022/9/6 23:24:12 人评论 次浏览 -
扫描线
扫描线的一些经典应用：求n个矩形的面积并和周长并。面积并（P5490 【模板】扫描线）首先扫描线的思想就是假设有一条无限长度的线从一个方向到另一个方向扫一遍整个图形，这样这个图形就变成了一大堆小矩形，然后算每个矩形的面积。这个过程可以上棵线段树。 怎么搞？首先…
2022/9/3 23:22:59 人评论 次浏览 -
树的难题 BJOI2017 点分治 单调队列
P3714 [BJOI2017]树的难题 没时间码 先口胡。 明显有一个n^2的暴力。可以拿到20分。 链的情况也非常容易 一个简单的单调队列 就可以解决 当然可以暴力的采用线段树。 这样可以拿到40分。 对于60分 直接考虑线段树合并 利用线段树维护每种颜色的最大值 由于不考虑边数问题…
2022/8/30 23:52:53 人评论 次浏览 -
NOI 2022 众数
1.前言 首先是：关于 \(\rm deque\) ，他死了但没有完全死。 然后是这个大样例说实话有点离谱，最初我在写 \(75\ \rm pts\) 部分分的时候，我动态开点线段树的 \(\rm insert\) ，没有处理好可能会有点被重复使用。我当时没意识到这个问题，就在操作四的时候人为对两个序…
2022/8/30 6:23:36 人评论 次浏览 -
线段树 C++实现 树形式
网上看了一圈，看到几个都是用数组实现的 我用树结构重写了一遍 #ifndef SEGMENTTREE_H #define SEGMENTTREE_H #include <vector>template<typename T> class SegmentTree {public:SegmentTree(std::vector<T> &a) {int N = a.size();this->a =…
2022/8/29 14:24:33 人评论 次浏览 -
模拟赛 矩形 （扫描线，三维偏序，线段树合并，并查集，线段树上二分）
PRO 题目大意：给定$N$个矩形，求连通块个数。($1 \leq N,x_1,x_2,y_1,y_2 \leq 100000$) SOL 乍一看就能知道是扫描线，不过这题的细节恐怖的要命。 （std同样看不懂，自己魔改了一下） 首先把完全相同的矩形去掉。 之后咱们可以发现，被其他矩形完全包含的小矩形对答案没…
2022/8/29 6:24:02 人评论 次浏览 -
线段树
线段树真是太强啦! 用途 线段树不同与树状数组,他支持单点查询,单点修改,区间修改,区间查询,需要 \(4\) 个函数进行,分别为 \(build,updata,query,lazy\) 组成,即搭建,更新,查询,懒惰数组。 build 建树 定义一个数组,我们称为 \(tree\) 对于 \(tree_i\) 我们同样保留 \(4\…
2022/8/29 6:23:56 人评论 次浏览 -
洛谷 P6242 【模板】线段树 3 吉司机线段树 区间取最小值 维护历史最大值和区间和
题目背景本题是线段树维护区间最值操作与区间历史最值的模板。题目描述给出一个长度为 nn 的数列 AA，同时定义一个辅助数组 BB，BB 开始与 AA 完全相同。接下来进行了 mm 次操作，操作有五种类型，按以下格式给出：1 l r k：对于所有的 i\in[l,r]i∈[l,r]，将 A_iAi 加…
2022/8/16 6:23:25 人评论 次浏览 -
2022.8.13 颓废记录
Preface 最后一天~ Content [CF1175E]Minimal Segment Cover给定形如 \([l,r]\) 的 \(n\) 条线段。\(m\) 次询问，询问每次至少选几条线段才能使它们的并集包含线段 \([x,y]\)。无解输出 \(-1\)。 \(1\le n,m\le 2\times 10^5,0 \le l\lt r\le 5\times 10^5,0\le x\lt y \…
2022/8/14 6:23:09 人评论 次浏览 -
线段树入门
简介 常用来维护区间信息的数据结构，可以在\(Olog(n)\)的时间内实现区间修改，区间信息合并，单点修改。 结构 建树 注意：线段树空间需要开到四倍。 struct Node {int minv; } seg[N * 4];// 根据左右儿子更新父亲节点信息 void update(int id) {seg[id].minv = min(seg…
2022/8/11 6:27:07 人评论 次浏览 -
编程兔暑假3.5阶段集训Day3——线段树后半部分、可持久化线段树、树状数组、倍增求LCA、树上差分、三种剖分以及搜索
我们接着昨天的讲。懒标记是线段树中一个十分重要的知识点，在线段树中进行区间修改时，暴力的做法是递归到叶子结点修改信息，复杂度达到了O(n) ，不过我们可以将这些修改操作攒起来，到了合适的时候一起修改，这就是懒标记。对于线段树上的每一个结点，引入一个标记，记…
2022/7/28 1:52:55 人评论 次浏览 -
LG6144 [USACO20FEB]Help Yourself P【DP，组合数，线段树】
传送门 思路 考虑 DP，设 \(f_{i,j,k}\) 表示前 \(i\) 条线段，连通块最右端的点为 \(j\) 的所有子集的连通块个数的 \(k\) 次方之和。初值 \(f_{0,0,0} = 1\)，答案为 \(\sum f_{n,j,K}\)。 把线段按照左端点排序，考虑加入第 \(i\) 条线段后对答案的影响，设 \(j\) 为加…
2022/7/23 23:24:43 人评论 次浏览 -
[学习笔记]李超线段树
这个之前学过的，结果我发现我忘了，怕之后再忘，我就再写一下吧。毕竟这个东西非常有用(好写)可以代替cdq/平衡树+斜率优化，来优化dp流程 数据结构本质是一棵线段树，每个节点都储存了\(bst[]\)。 \(bst[l,r]\)表示覆盖该点范围的在\(mid\)处取最值的线段。 你会想：维护…
2022/7/12 23:22:11 人评论 次浏览 -
SD
D1T1 树形 \(\text{DP}\)。 令 \(f_{u,s,k},(k\in\{0,1\})\) 表示仅考虑以点 \(u\) 为根的子树，固定 \(u\) 的权值为 \(s\)，\(u\) 子树中是否有点的权比 \(u\) 的权大的方案数。 \[\begin{aligned}\\ f_{u,s,0}&=\sum_{v\in\operatorname{son}(u)}\sum_{w\in\operat…
2022/6/19 23:23:39 人评论 次浏览
