埃兰希尔

分类

线段树(1) 题解(7)

/ 注册

全部文章（共6篇）

线段树合并模拟

节选自我的博客 NC15557 连续区间的最大公约数这道题没有修改，只有查询。查询最大公约数还是比较简单的，但是查询子区间的最大公约数也等于整个区间的最大公约数的数量，这就不这么快乐了。假设我们两个孩子区间的和他们子区间满足条件的数目，要合并成父亲区间，父亲区间的就是对两孩子...

线段树

2020-08-05

2 550

线段树合并模拟

节选自我的博客牛客网：NC20279 [SCOI2010]序列操作洛谷：P2572 [SCOI2010]序列操作牛客做的人比较少，建议在洛谷上做。 3个操作，2个查询，线段树模拟大题。来想一想要维护什么信息。首先，和在这道题中反复转换，所以每种信息肯定给和分别维护一...

线段树

2020-08-05

2 476

线段树差分和最大公约数

更好的阅读体验简述概念和应用所谓的差分，其实就是后一项与前一项的差，对于第一项而言，。设数组，那么差分数组，即 ,那么， NC26255 小阳的贝壳这题要求最大公因数和差分最值，最值上一题已经求过了，这最大公因数怎么维护出来呢？而且修改是区间修改的，这貌似也增加了...

线段树

2020-08-04

3 610

线段树差分

更好的阅读体验简述概念和应用所谓的差分，其实就是后一项与前一项的差，对于第一项而言，。设数组，那么差分数组，即 ,那么，差分在线段树和树状数组上应用很广泛。关于树状数组的差分可以用来解决“区间修改，单点查询”的问题，在我上一篇博客讲树状数组入门时有分析，题目是P336...

线段树

2020-08-04

7 812

线段树和树状数组学习笔记

更好的阅读体验学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是级别的数据结构的美，但是做起题来还是相当痛苦的（特别是一开始只会模板的时候，很难灵活运用线段树的性质）。还好有雨巨大神带入门，视频讲解十分直观（b站上也有很多介绍线段树的视频），不用像以前一样看各种博客题解入...

树状数组线段树

2020-08-02

0 640

线段树RMQ问题

听说博客观看效果更佳这道题是比较经典的问题,找到X和Y年间的最值来进行判断真假 , 用线段树维护是比较简单好写的。然而这只是一个小判断，比较难的是判断。如果没有想好直接打代码会调很久（没错就是我）。怎么维护查询区间最大值我就不再这里赘述了，不懂线段树的先去入门（此题也是线段树入门...

线段树

2020-07-31

1 529