当前位置:首页 > 数据结构 > 线段树 > 正文
HDU1754IHateIt
4633+

题目大意:学生的成绩经常会变,老师们很喜欢询问,从x号到y号当中,分数最高的是多少,如何快速回答?

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试,请处理到文件结束。

在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。

学生ID编号分别从1编到N。

第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ,和两个正整数A,B。

当C为’Q’的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。

当C为’U’的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作,在一行里面输出最高成绩。

Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9

解题思路

如下图,把1到n个学生看成一条[1,n]的线段,如果线段长度超过1,不断地分成2半,直到长度为1。题目要求回答区间最大值,那么我们每一条线段就记录该区间的最大值。

首先是单点修改:修改的时候,我们可以递归找到对应的长度为1的线段,如修改第k个学生的成绩,那么找到线段[k,k],修改他的值即可。长度为1的值被修改了,有可能影响到包含它的线段的最大值,故在回溯的时候,即搜索完左右儿子后,需要更新父亲结点的最大值。由于每次分成两半,递归深度在log2n范围内,每次修改时间复杂度是O(log2n)。

其次是回答询问:如询问[x,y]区间的最大值,我们可以从根结点开始搜索,如果[x,y]完全包含根结点,那么我们不需要在往下找了,因为根结点下面的所有节点的最大值以及记录在根结点;如果并不是完全包含,则左边包含就往左边找左边的最大值,右边包含就往右边找右边的最大值,最终取这两个值的最大值即可。对于每次询问,时间复杂度也是O(log2n),因为如果询问的区间很大,两边都有,那么左右两边的复杂度是一样的。现在只看左边的结点,如果左边的结点也是两边都有包含,那么右边区间可以直接返回;如果只是右边被包含,左边不需要搜索。也就是说,不会出现左右两边一起往下扩展的情况

程序实现

堆结构存储:堆结构存储的优点是不需要记录该结点的左儿子、右儿子是谁,因为如果该结点变化是p,那么左儿子就是p*2,右儿子就是p*2+1。那么,数组开多大呢?4倍是不会出错的,为什么2被不行呢?从线段树的结构图可以看出,最后一层可能会突出几个叶子结点,层数是⌈log2n⌉+1,因此我们至少需要开1<<⌈log2n⌉+1大的数组(最后一层结点数是1<<⌈log2n⌉,所有层结点数需要再乘以2)。

结构体链表+动态开点:用结构体链表存储,只需要开2倍的数组就行,因为每个长度为1的点占一条线段,之后两两合并:n+n/2+n/4+…+1。动态开点,就是用到他的时候才给该结点分配空间:一开始根结点p是0,c记录当前分配了多少个结点,如果出现p=0即还没分配空间,此时++c的编号的结构体就分配给该结点;同样地,当需要进入儿子结点的时候,直接把记录儿子结点的编号的变量传过去就行,如果该编号为0,递归进入后会给他分配空间,由于传参数用的是引用(&p),那么父亲结点对应的变量会自动修改。

为什么不需要记录线段的左右端点呢?因为在递归搜索的过程中,传参数的时候可以顺便计算出区间的左右端点,不记录左右端点可以节省空间。如果询问q远比区间n+1小,那么可以开更小的空间,因为每次查改,都是是一条链下去的,是log级别的,空间开到q*log2(n+1)*2就足够了。

紧凑存储:堆结构存储之所以浪费空间,是因为最后一层空了很多个出来,其实我们可以采用更紧凑的存储方式——每个区间[l,r]分别存储在数组中的l+r位置上。叶子结点的区间都是[i,i]的形式,那就存储在2,4,6,8……中间的空位恰好可以存储他们的父亲结点,如果出现区间[1,3],会存在4产生冲突,那么我们规定非叶子结点都放在奇数上,即区间l!=r那么|1变成奇数,因此对于区间[l,r]的存放位置就是(l+r)|(l!=r)。

分块代码,复杂度更高,但实际速度最快:

HDU1754IHateIt:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!