shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共14篇）

窗内的星星来自专栏

题目意思很简单,就是你拿一个给定大小的矩形去圈星星,要求你圈到星星最大的亮度是?这题可以直接二维曲尺解决,因为数据不是很强,但是我们还是讲讲线段树如何解决.还是和上题一样用线段树的扫描线解决,我们把数据做成给定坐标和价值做成扫描线,扫描完了就抛弃,把线段树存节点存成线段,然后我们用add做延迟标记,...

线段树离散化

2020-07-20

2 683

亚特兰蒂斯来自专栏

讲这题之前,我先介绍下线段树扫描线,可能昨晚睡眠不足,导致今天连递归都没看懂,服了.扫描线只是利用线段树思路解决问题的一种方式而已.就拿本题来说要你计算图形面积.这是题目的样例,讲下重点和我对这题的理解，虽然不是很透彻..首先我们可以把x轴按x的值切分，我们要用y轴值进行快速更新.首先这个更新可以用...

线段树离散化

2020-07-20

2 714

区间最大公约数来自专栏

思路:求l~r的a数组的gcd,等价于求al与各差分ai的gcd.证明:辗转相除法.详细的讲下吧.假如d是al,al+1...ar的gcd,那么它一定是al,al+1-al,al+2-al+1...的公约数.同理后面可得前面.那么原题就可以用线段树维护差分数组的gcd即可.代码如下: #includ...

线段树

2020-07-19

2 650

你能回答这些问题吗来自专栏

怀着激动的心情,把大家都会的线段树学了一下.听说线段树博大精深,所以决定把进阶指南暂时放一放,学完这个把kuangbin的线段树专题也做了.emm.今天先更个不带lazy的线段树,虽然我觉得带不带lazy其实都差不多.但是,第一次写线段树,好激动哎...首先介绍线段树的几个操作(不带lazy).1....

线段树

2020-07-19

3 670