线段树 – Tgotp-Blog

1645: [Usaco2007 Open]City Horizon 城市地平线

没注意到是左闭右开区间…卡了半天。
考虑用线段树可以很好的维护区间信息,那么考虑使用线段树。
对于区间max很明显可以随便维护。
重点在于数据范围1e9,考虑离散化,
若令tru[i]表示把一个数离散成i这个数与他上一个数的差值,
那么只用在统计答案的时候再乘以这个值即可。
但是略微[……]

Read more

2892: 强袭作战

同1171

c++代码如下:

 

1171: 大sz的游戏

线段树每个节点维护两个list t1,t2,分别代表这个区间里最小话费(单调递增)以及包含这个区间的最小花费(单调递增)

然后查询先去掉超过L的就搞定了。

c++代码如下:

 

NOIP2017 题解

终于开始在晚自习的时候填填noip的坑了。

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

推规律(找规律),a*b-a-b;

c++代码如下:[……]

Read more

3685: 普通van Emde Boas树

线段树模板题(伪

交了x遍,细节处理一定要注意,TAT

c++代码如下:

 

Distance

题目链接:https://www.nowcoder.com/acm/contest/16/B

TGSteven大佬说是智障题,所以我成了智障了。。。

整场比赛就写了1,2题,而且这题还是最后做出来的。

如果没有绝对值,无疑是大水题。

然后有绝对值的话,只用分类讨论即可。[……]

Read more

3110: [Zjoi2013]K大数查询

整体二分,用线段树维护区间大于mid 的值

c++代码如下:

 

1798: [Ahoi2009]Seq 维护序列seq

注意:先乘后加!!!!QAQ

c++代码如下:

bzoj2733 [HNOI2012]永无乡

第一次写线段树合并,照着黄学长的blog打的。http://hzwer.com/3944.html

对于这道题,因为每个点的重要度是唯一且确定的,所以记录权值,然后合并的时候只用沿着其中一个线段树,并将另外一颗线段树拥有这个线段树所没有的边连上来就好了。

然后更新一下,搞定。当然还可以用[……]

Read more

BZOJ1067: [SCOI2007]降雨量

时隔半个月写的第一题,还是改的原来的。。。

这道题算法很显而易见,重点在于细节处理。

建代码的处理咯

c++代码如下: