题目描述
老师想知道从某某同学当中，分数最高的是多少，现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩.
输入描述：
每组输入第一行是两个正整数N和M（0 < N <= 30000,0 < M < 5000）,分别代表学生的数目和操作的数目。
学生ID编号从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩
接下来又M行，每一行有一个字符C（只取‘Q’或‘U’），和两个正整数A,B,当C为'Q'的时候, 表示这是一条询问操作，假设A(后面没有了，是牛客网该题bug，但是根据样例可以猜测，补充如下)
假设A,B为学生ID，表示查询该范围内学生的最大值。（有个小坑，因为A不一定小于B）
当C为'U'的时候, 表示这是一条更新操作，假设A为学生ID,B为学生更新后的成绩。
输出描述：
对于每一次询问操作，在一行里面输出最高成绩.
示例1
输入例子：
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
输出例子：
5
6
5
9示例2
输入例子：
3 2
1 2 3
U 2 8
Q 3 1
输出例子：
8链接：
牛客网华为2016机试题 第一题
思考方向
我当初是参考这道题，307. 区域和检索 - 数组可修改学习了线段树，后面修改了代码提交该题。
Python
Python
# 307. 区域和检索 - 数组可修改 模版题
class NumArray:
def buildtree(self,k,l,r):
if l==r:
self.f[k] = self.nums[l]
return
m = (l+r)>>1
self.buildtree(k+k,l,m)
self.buildtree(k+k+1,m+1,r)
self.f[k] = self.f[k+k]+self.f[k+k+1]
def add(self,k,l,r,x,y):
self.f[k]+=y
if l==r:
return
m = (l+r)>>1
if x<=m:
self.add(k+k,l,m,x,y)
else:
self.add(k+k+1,m+1,r,x,y)
def query(self,k,l,r,s,t):
if l==s and r==t:
return self.f[k]
m = (l+r)>>1
if t<=m:
return self.query(k+k,l,m,s,t)
else:
if s>m:
return self.query(k+k+1,m+1,r,s,t)
else:
return self.query(k+k,l,m,s,m)+self.query(k+k+1,m+1,r,m+1,t)
def __init__(self, nums: List[int]):
n = len(nums)
self.nums = [0]+nums
self.n = n
self.f = [0]*(4*n)
self.buildtree(1,1,n)
def update(self, index: int, val: int) -> None:
self.add(1,1,self.n,index+1,val-self.nums[index+1])
self.nums[index+1]=val
return
def sumRange(self, left: int, right: int) -> int:
return self.query(1,1,self.n,left+1,right+1)
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)需要帮助的地方
测试用例通过不了
修改后代码
感谢@Yawn_Sean。
原因是之前update写错了。修改如下：
Python
Python
# 307. 区域和检索 - 数组可修改 模版题
class NumArray:
def _buildtree(self,k,l,r):
if l==r:
self.f[k] = self.nums[l]
return
m = (l+r)>>1
self._buildtree(k+k,l,m)
self._buildtree(k+k+1,m+1,r)
self.f[k] = self.f[k+k]+self.f[k+k+1]
def _update(self,k,l,r,x,y):
if l==r:
self.f[k]=y
return
m = (l+r)>>1
if x<=m:
self._update(k+k,l,m,x,y)
else:
self._update(k+k+1,m+1,r,x,y)
self.f[k] = self.f[k+k]+self.f[k+k+1]
def _query(self,k,l,r,s,t):
if l==s and r==t:
return self.f[k]
m = (l+r)>>1
if t<=m:
return self._query(k+k,l,m,s,t)
else:
if s>m:
return self._query(k+k+1,m+1,r,s,t)
else:
return self._query(k+k,l,m,s,m)+self._query(k+k+1,m+1,r,m+1,t)
def __init__(self, nums: List[int]):
n = len(nums)
self.nums = [0]+nums
self.n = n
self.f = [0]*(4*n)
self._buildtree(1,1,n)
def update(self, index: int, val: int) -> None:
self._update(1,1,self.n,index+1,val)
self.nums[index+1]=val
return
def sumRange(self, left: int, right: int) -> int:
return self._query(1,1,self.n,left+1,right+1)
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)
评论 (3)
