线段树 – Tgotp-Blog

4552: [Tjoi2016&Heoi2016]排序

对于单独的一个数字可以用线段树搞,那么考虑二分一个数字

最后看q这个位置上数字的大小关系即可

c++代码如下:

 

3211: 花神游历各国

水题,容易发现开根很少次数就始终为1了

暴力线段树即可

c++代码如下:

 

4653: [Noi2016]区间

水题,离散化一波然后线段树。

c++代码如下:

 

#2472. 「九省联考 2018」IIIDX

一眼思路的题…
就是比较难写..

考虑一个点必须小于其 \lfloor \frac{id}{k} \rfloor 那么容易想出一个树形结构,每个点都大于其父亲.
那么对于一个点,那么他能选取的最大值就是当前能选的所有点中的 n - size[id]这个点的值。
然后留够其[......]

Read more

4817: [Sdoi2017]树点涂色

c++代码如下:

 

4293: [PA2015]Siano

观察了一下...

发现我现在blog流量比原来高了好多...

原本这个blog因为各种原因都半弃坑了...

(转csdn了以及跳转到了钓鱼网站等原因...

但是现在因为这些问题莫名好了?

我还是保持两个地方的代码同步把...

去成都考试的题目的原题?
思路是一眼[......]

Read more

1058: [ZJOI2007]报表统计

读题观察发现:

操作一只用一个平衡数维护单调区间即可。

且差值绝对值变化一定是变小,那么在插入的时候更新即可。

操作二只用一个线段树维护区间最小值即可.

观察发现在某个位置增加数以后更改的差值只与这个位置上一次操作的数有关,以及下一个位置的第一个数有关.

线段树维护即可[......]

Read more

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

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

Read more

2892: 强袭作战

同1171

c++代码如下:

 

1171: 大sz的游戏

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

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

c++代码如下: