寒江陪烟火🔥

线段树

acm相关(6) dp(68) RMQ(5) STL(6) 主席树(2) 二分匹配(23) 二分查找(2) 分治法(3) 划分树(1) 单调队列(2) 博弈(11) 字典树(3) 字符串处理(1) 学习(1) 并查集(4) 强联通分量(3) 归并排序(1) 拓扑排序(1) 搜索(1) 数论(8) 最小生成树(3) 最短路(5) 树状数组(7) 树链剖分(4) 欧拉回路(5) 简单模版(14) 简单题(24) 网络流(6)

/ 注册

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

bzoj1012 最大数maxnumber（线段树）

题意： Description 　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如...

2016-09-08

0 358

SDUTOJ1755 装备合成（dfs序+线段树）

题目描述小白很喜欢玩儿LOL，但是无奈自己是个坑货，特别是在装备的选择和合成上，总是站在泉水里为选装备而浪费时间。现在小白试图解决这个问题，为了使问题简单化，我们把游戏中的装备合成规则简化如下：（1）装备的合成关系构成一棵合成关系树，如图(a)所示，装备的下级装备叫合...

2016-05-31

0 250

SDUTOJ2880 Devour Magic（线段树两重延迟标记）

题意：每个点能量每秒加1 按时间顺序给你N组时间+区间表示在时间t时取走区间内的能量问取走了多少能量思路：区间修改区间查询加能量数延迟一下去走后延迟一下用两个flag保存延迟状态 /* ************************************...

2016-05-14

0 241

SDUSTOJ 1796 哆啦A梦的军队（线段树维护前缀位置）

Description 在2050年机器人战争爆发，聪明的机器猫为了帮助大雄打赢这场战争，从自己口袋里掏出了机器人战棋，每一个战棋都可以成为一名战士，哆啦A梦决定给他们整整队，哆啦A梦发现第 i 个位置的战士编号为 Ai（显然 A 是一个排列）。经过计算，哆啦A梦发现，让第 i 个位置的战士...

2016-04-26

0 349

FZU1608（线段树成段更新，区间求和pushdown延迟标记结构体版）

题意：给了你一些区间，x,y,第三个参数w是效率，代表这段时间他的单位时间效率，效率总和就是 (y-x)*w，然后有的时间段会被重复啊，比如前面给了1,4,1，后面又给了2,4,3他们为了是的时间段1,4的效率总和最大肯定是选择 2，4区间的效率值选择3，意思就是后面出现更好的情况就覆盖...

2015-11-01

0 272

POJ2667 Hotel（线段树区间合并）

这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边 2 a b:将[a,a+b-1]的房间清空思路:记录区间中最长的空房间线段树操作:update:区间替换 query:询问满足条件的...

2015-08-22

0 246

POJ2528 Mayor's posters（线段树成段替换，区间查询，离散化简单hash）

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报思路:这题数据范围很大,直接搞超时+超内存,需要离散化: 离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][200...

2015-08-21

0 205

POJ3468 A Simple Problem with Integers（线段树成段增减，区间求和）

题意：一个数列，每次操作可以是将某区间数字都加上一个相同的整数，也可以是询问一个区间中所有数字的和。（这里区间指的是数列中连续的若干个数）对每次询问给出结果。 #include <iostream> #include <cstdio> #include <cst...

2015-08-21

0 221

HDU1698 Just a Hook（线段树成段替换、区间求和，延迟标记的应用）

题意：胖子有一条大jb，大JB由n个小JB组成，每次操作将一个区间的小JB变成金银铜三者之一，最后取出所有区间的JB总价值思路：和刷气球差不多意思了，简单的区间更新，无需更新到叶子节点，防止超时 #include <iostream> #include <cstdio&...

2015-08-20

0 210

HDU2795 Billboard（线段树基础题单节点更新区间查询）

题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子思路:每次找到最大值的位子,然后减去L 线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了) #include <iostream> #include <c...

2015-08-20

0 276