生之、如舟

线段树

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 蓝桥杯(1) 贪心(1)

/ 注册

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

HDU4217 Data Structure? 【权值线段树】来自专栏

Data Structure? 题目链接：https://vjudge.net/problem/HDU-4217 思路主要就是这段话：以查询第k大为例，权值线段树的核心是到每个结点，如果右子树的权值总和大于了k，则说明其第k大值在右子树，递归进入右子树。反之则说明第k大值在左子树。特别注意：若要...

线段树

2020-04-12

0 676

P1637 三元上升子序列【权值线段树】来自专栏

P1637 三元上升子序列题目链接：https://www.luogu.com.cn/problem/P1637 思路 Lcnt[i]表示位置i，左边有多少个小于arr[i]Rcnt[i]表示位置i，右边有多少个大于arr[i]所以左右可以分别进行搞一次权值线段树，线段树存的是[l,r]之间的元素...

线段树

2020-04-12

0 717

HDU1394 Minimum Inversion Number 【权值线段树】来自专栏

Minimum Inversion Number 题目链接：https://vjudge.net/problem/HDU-1394 思路在线段树中维护每个数当前出现的次数，然后一个一个添加，每次添加前看有多少个数是大于自己的，然后加在逆序对总数上面就行。之后再循环一边，因为是把第一个放在最后面去，...

线段树

2020-04-12

0 659

CF624div3-F. Moving Points 【线段树】【离散化】

CF624div3-F. Moving Points 题目意思很简单，就是在一个x轴上，有N个有速度的点，他们可以向左向右的速度，问在之后的移动过程中，两两点点距离差之和最小是多少。分析因为这是一个匀速运动，我们不妨把两个匀速运动方程做差，做差之后的运动方程就是就是两个点运动过程中的距离之差方...

线段树

2020-03-01

0 988

HDU4027-Can you answer these queries? 【线段树】【暴力】

Can you answer these queries? 题目给定N个元素，操作M次区间修改和区间查询，区间修改是把区间内所有元素各自进行开方，区间查询是查询这个区间的和。初始元素小于分析对于此题，开方的操作是很难上下传递的，而我们知道开方速度是很快的，我测了一下1e18开方只需要6次，所以...

线段树

2020-02-28

0 674

ZOJ1610-Count the Colors 【线段树】【区间覆盖】【区间合并】

Count the Colors 题目在[0,8000]区间进行N次区间染色，后涂的色可以覆盖之前涂的色，问N次染色之后，能看见的颜***间数量各是多少？分析其实这题区间覆盖这部分很好做，不需要离散化，因为只有8000长度的区间。我们要注意的是，需要将区间改成左开右闭的形式，比如给[0,2]，...

线段树

2020-02-28

0 1235

HDU2528-Mayor's posters 【线段树】【区间覆盖】【离散化+插点】

Mayor's posters 题目有一面墙，现在有M张海报要贴，海报的高度和墙的高度一样，每张海报会给出区间范围[l,r]，问最终墙上可见的海报有多少张？墙的宽度: 分析首先这题的墙的范围很大，所以必须离散化，然后在离散化之后的数据上建立线段树。要点这题对于染色后连续的区间[l,r]有可能...

线段树

2020-02-28

0 706

HDU1698-Just a Hook 【线段树】【区间覆盖】

Just a Hook 题目给定一个区间[1,N]，里面的元素都是1，现在有M次区间修改的操作，每次会选择一个区间将其置为1或2，或3，问最后区间[1,N]的元素总和为多少？分析这是一道典型的区间覆盖问题，用线段树可以很好的解决。只需要在定义结点的时候，加上sum和tag就行。sum表示此结点...

线段树

2020-02-28

0 974

acwing243. 一个简单的整数问题2 【线段树区间修改】【模板】

243. 一个简单的整数问题2 AC代码 #include <iostream> #include <cmath> #include <cstring> using namespace std; const int maxn = 1e6+10; typedef...

2020-02-27

0 607

1264. 动态求连续区间和【模板】【线段树】

1264. 动态求连续区间和题目描述给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。输入格式第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。第二行包含 n 个整数，表示完整数列。接下来 m 行，每行包含三个整数 k,a,b （...

线段树

2020-02-02

0 694