segmenttree

题目选讲

• 你能回答这些问题吗 ⭐⭐⭐
  • 题意：给出n个数，和m个操作，一个操作是问l到r区间最大的连续字段和是多少，另一个操作是单点修改。
  • 题解：使用线段数维护区间的sum，lmax，rmax，max。那么p.sum = l.sum + r.sum, p.lmax = max(l.lmax, l.sum + r.lmax), p.rmax = max(r.rmax, r.sum + l.rmax), p.max = max(max(l.max, r.max), l.rmax + r.lmax)。画一下线段树图，很容易理解。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH4301.cpp
• Colonial Mansions：https://codeforces.com/gym/101962/problem/I⭐⭐⭐⭐
  • 题意：给n个房屋，高度是h[]，第i个房屋可以去第i-1和第i+1个房屋，单点修改房屋高度，查询操作，输入i，h，问第i个房屋可以去那些房屋（满足相邻的房屋高度差小于h即可去)
  • 题解：线段树维护差分序列，对于查询操作其实就是问从i房屋向左向右序列一直小于等于h的个数。我们可以维护差分序列的区间最大值，然后二分查找向左向右扩展的距离。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf101962I.cpp