线段4578 hdu
线段树练习
# Ⅰ.差分与前缀和 ## P2184 贪婪大陆 **题意** :给定防线长度 $n$ 和操作次数 $m$, 每次在 [$l$ ,$r$] 内布下一种雷,查询区间雷的种类数。 **分析** : 用线段的方式表示区间布的雷 : ![](https://cdn.luogu.com.cn/upload/i ......
HDU #6664. Andy and Maze 题解--zhengjun
对每个点随机黑白染色,强制答案链的前 \(\lfloor \frac{k}{2}\rfloor\) 个点和后 \(\lceil \frac{k}{2} \rceil\) 个点的颜色不同。 计算答案只需要枚举中间这条两端颜色不同的边 \((u,v,w)\),然后分成两边计算 \(u,v\) 出发的经过 ......
hdu 6397 Character Encoding 容斥
我是链接 刷刷计数防止大脑萎缩 题意:给定n,m,k,要求我们选m个范围在[0,n−1]中的数,使得这m个数的和为k 其中n,m,k都是10^5以内 如果没有范围在[0,n−1]的限制,就是小球与盒子经典例题,答案就是C(k+m-1,m-1) 有这个限制的话,考虑容斥,我们强制1个数不合法(其他的数 ......
李超线段树
李超线段树 李超线段树是一种求函数定点最值的线段树,思路高妙,用处也很广。 以模板题为例。 P4097 [HEOI2013] Segment 有 \(n\) 个操作,操作分两种。 在平面上加入一条线段,两端端点为 \((x_0,y_0)\) 和 \((x_1,y_1)\),第 \(i\) 条被插入的 ......
双向广搜-> hdu1195
问题描述:密码锁有起始和目标两个状态,状态有4个连续数字,数字范围是1~9。其中特殊情况9 + 1 = 0, 1 - 1 = 9。 每次操作可以交换相邻的两个锁上的数字,或者将该位上数字±1。求最小操作次数 分析:是一道双向广搜的题,但是这个题目的第一个思路就是枚举所有的排列组合状态,然后对每个状态 ......
数据结构 - 线段树学习笔记
前言 果果终于讲线段树了 线段树太 TM 好用啦! But,强大的功能是需要码量来实现的。 定义 线段树是一种储存了一个序列的区间信息,并在各个区间中建立了关联的数据结构。 对于任意一个序列都可以建出它的线段树。 它是一颗完全二叉树,它的每一个节点都是一个区间。 对于每一个节点,其左儿子节点为这段区 ......
HDU1823 Luck and Love 题解
Question Luck and Love 小 \(w\) 征婚,收到很多女生报名,小 \(w\) 想找到最有缘分的女生,有 \(t\) 组操作 I H A L,\(H\) 表示身高,\(A\) 表示活泼度,\(L\) 表示好感度 Q H1 H2 A1 A2 表示身高和活泼度的范围,需要在这个范围 ......
HDU1540 Tunnel Warfare 题解
Question HDU1540 Tunnel Warfare 在一条线上有 \(n\) 个村庄,两个相邻的村庄之间用地道连接,做 \(m\) 次操作 D x 第 \(x\) 个村庄被摧毁,它的地道也一同被摧毁 Q x 查询第 \(x\) 个村庄所能到达的村庄总数(包括村庄 \(x\)) R 重建刚 ......
浅谈几类线段树、树状数组优化 DP
本文主要介绍几类线段树和树状数组优化动态规划的方法。 本文的理论部分比较简单,所以主要以题目讲解为主。 这是本蒟蒻的第一篇日报,如有问题,请指出,感谢。 Part 0. 前置知识 动态规划 线段树 Part 1. 属性在一个区间的进行转移 这是讨论的是形如 \(f_i=Y(i)+\max\limit ......
HDU4614 Vases and Flowers 题解
Question HDU4614 Vases and Flowers 有 \(n\) 只花瓶,一只花瓶中只能插一朵花,Alice 经常收到很多花并插到花瓶中,她也经常清理花瓶 1 A F 表示收到了 \(F\) 朵花,从第 \(A\) 只花瓶开始插,如果花瓶中原来有花,就跳过去插下一只花瓶,如果插到 ......
线段树
线段树 引入 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 \(O(\log N)\) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。 线段树 线段树的基本结构与建树 过程 线段树将每个长度不为 \(1\) 的区间划分成左右两 ......
HDU2544 最短路 题解 Bellman-Ford算法
题目链接:https://acm.hdu.edu.cn/showproblem.php?pid=2544 题目大意:一道简单的最短路。主要是记录一下 bellman-ford 算法的实现。 示例程序(bellman-ford): #include <bits/stdc++.h> using name ......
P3372 【模板】线段树 1
原题链接 题后感 码量也太大了吧 小记 题解网上有,但是有关这个lazytag我要提一嘴,我建议不要记它,你只需知道修改的区间没有整体破坏时,其内部的元素内容暂不做修改 code 码量真大 #include<bits/stdc++.h> #define ll long long using name ......
P10009 [集训队互测 2022] 线段树 题解
题目链接:P10009 [集训队互测 2022] 线段树 神仙分块题,先给一下出题人的神仙官解:官解 前面还看得懂。后面是啥?这不是 ds 题咋和 dp、轮廓线扯上关系了。看了半天,还是这个启发了我: 其手玩下,在 Excel 里写一下,可以理解到这里其实是想表达的一个核心意思是啥:对于一组序列而言 ......
Rust实现线段树和懒标记
参考各家代码,用Rust实现了线段树和懒标记。 由于使用了泛型,很多操作都要用闭包自定义实现。 看代码。 // 线段树定义 pub struct SegmentTree<T: Clone> { pub data: Vec<T>, tree: Vec<Option<T>>, marker: Vec<T ......
线段树笔记
例\(1\) 题目描述 给定一个长为\(n\)的序列,有\(m\)次操作,每次操作为以下三种之一。 修改序列中的一个数 求序列中某连续一段所有数的两两乘积的和\(\text{mod} 1000000007\)。 求序列中某连续一段所有相邻两数乘积的和\(\text{mod} 1000000007\) ......
hdu-acm新生赛-智能车
原题链接 前言 考场上想了半天,用了好多种思路,最后用背包类一维数组加上最大的最小值记忆化求解。 思路 我一开始想的思路,就不说了,直接说我最终解法是怎么得到的。 我想什么时候无法启动智能车,即判断存不存在电池的组合使得刚好达到所需电力? ......
【模板】李超线段树 / [HEOI2013] Segment
李超线段树是一种用于维护平面直角坐标系内线段关系的数据结构,插入直线/线段,支持查询单点极值 李超树的经典应用是斜率优化,可以看下这篇文章 李超线段树没有用懒标记实现区间修改,而用的是标记永久化 其实标记永久化与我们对lazy标记的理解非常相同,可以看看LYD蓝书上对标记永久化的解释,都是累积某个节 ......
HDU 1404 ”Solitaire“ (双向广搜)
HDU 1404 ”Solitaire" OJ:https://acm.hdu.edu.cn/showproblem.php?pid=1401 题目大意:8 * 8 的棋盘,上面有四个棋子,棋子可以上下左右移动,如果在上下左右移动的时候该位置有一个棋子已经放置,可以跳过这个棋子放在后面,不可以连续跳 ......
lazy线段树模板
import java.io.*; import java.util.*; public class Main { static int N = (int)1e5+10; static long[] arr = new long[N]; static long[] sum = new long[N< ......
线段树板子
package ICPC; import java.util.*; import java.math.*; import java.io.*; import java.text.DecimalFormat; import java.text.NumberFormat; class node{ int ......
线段树 2
由于有两个操作,我们要对乘法和加法设置一个优先级 我们来看看先乘后加,lazy2表示乘数,lazy1表示加数(前者初始值为\(1\),后者初始值为\(0\)) 根据我们对lazy的理解,一个节点的和的真实值,为这个节点到根节点的路径中,对每一个节点依次先乘lazy2再加lazy1得到的最终结果 假设 ......
线段树例题
目录线段树例题P3372 【模板】线段树 1题目描述解题思路CodeP3373 【模板】线段树 2题目描述解题思路CodeP6492 [COCI2010-2011#6] STEP题目描述解题思路CodeP2184 贪婪大陆题目描述解题思路CodeP4588 [TJOI2018] 数学计算题目描述解题 ......
线段上离p最近的点 - 投影方式
判断依据 1) 投影结果<0,则线段端点a离p最近 2) 投影结果>线段ab的长度,则线段端点b离p最近 3) 否则p在线段上的垂点为最近点 p与ab不共线时 1) p在线段两侧 2-a) p在线段内侧 2-b) p在线段内侧2 p与ab共线时 1) p在线段两侧 2-a) p在线段内侧 2-b) ......
动态开点线段树如何开空间
昨天模拟赛开小了导致 \(100\to 70\) 沦为暴力同分。遂记之。 单点修改 \(m(\log V+\delta)\)。 区间修改 \(2m(\log V+\delta)\)。注意这个 \(2\),就很灵性啊。(欸真的是 \(2\) 嘛) 关键在于 1G 空间用了 200M 还乱开小空间的行为 ......
吉司机线段树
\(mxb\) 为历史最大值,\(tg1,tg2,tg3,tg4\) 分别对应最大值真实 \(tag\) ,其他值真实 \(tag\) ,最大值最大 \(tag\) ,其它值最大 \(tag\) #include<bits/stdc++.h> using namespace std; #define ......
线段树与历史最值和区间最值问题
线段树与历史最值问题 P4314 CPU 监控 Description 给定数组 \(\{a_i\}\),维护以下操作。定义一个辅助数组 \(\{b_i\}\),每次操作完后令 \(b_i=\max(a_i,b_i)\)。 查询 \(\max_{i=l}^{r} a_i\)(区间最值) 查询 \(\ ......
syoj.1827. 线段传送带题解
前情提要-三分 1827. 线段传送带 P2571 [SCOI2010] 传送带 省流:三分套三分。 在二维平面上有两个传送带,一个从 A 点到 B 点,一个从 C 点到 D 点,速度分别是 p 和 q,在平面内其他点的速度为 r。求 A 点到 D 点的最小速度。 考虑从 A 到 D 的路程一定是 ......
线段树详解
定义 什么是线段树 线段树是一种二叉搜索树,每个节点都存储了一个区间的问题。 能够解决的问题 序列维护修改以及查询区间上的最值、求和等,修改和查询的时间复杂度为 \(O\)(\(log\) \(n\))。 与其他 RMQ 算法的区别 算法 适用范围 优点 缺点 线段树 动态 可执行的操作多 常数大 ......