高级数据结构6.2——线段树

见闻

我感觉线段树是现在比赛里经常遇见、也很明显的一类问题。它用于解决给定一个大数组,然后对其中区间进行反复查询,也可能涉及求值、修改等操作,题目描述里查询次数超过105。是牺牲空间换取时间的方法。

要掌握这个需要先学习的相关知识。如果问题规模不大,我们可以使用树状数组的方式实现;如果问题规模很大,我们需要使用离散化,挺难的。这个讲的很好

 

相关练习

 

6.2.1 Lost Cows (2182)

题目描述:

n头牛编号为1…n,打乱顺序排成一列,除去队首的牛之外,给出每头牛在队列中前面编号比它小的牛的数量,求队列中每头牛的编号。

我们推一下样例输入:

5(一共 5 头牛,后面四行为牛牛打乱顺序后的随机排列)

1(第 2 头牛,前面编号比它小的数量为 1 。即第 1 头牛编号比它小)

2(第 3 头牛,前面编号比它小的数量为 2 。即 1 、2 头牛编号都比它小)

1(第 4 头牛,前面编号比它小的数量为 1 。它前面只有一头牛编号比它小)

0(第 5 头牛,前面编号比它小的数量为 0 。它比前面所有的牛牛编号都小,他是第 1 头牛牛)

即,[5]  [1]  [4]  [2]  [3]

        0           1    1    2

经过输入后面小括号内一系列的描述,可以得出随机排列时牛牛们的原本编号:

2

4

5

3

1

题目分析:

通过对样例的分析,我们不难得出(用 low 指代输入所表示的前面编号比它小的牛的数量):

最后一个位置的牛的编号为:low + 1

中间位置的牛的编号为:随机排序后面的牛在它前面的数量 + low + 1

然后我们用一个数组确定状态,根据输入逆推即可,据说这样暴力也可以过。

 

但是,这题我们 应该这样 练习吗?——不应该(三里三气)

 

高级数据结构6.2——线段树

上一篇:Shiro


下一篇:vue v-cloak妙用