这真是,又对着一棵线段树思考人生。== 蒟蒻如我比赛时如果碰到这种题是不是要直接弃疗了== 想的对也写不对><
线段树的每个节点记录两个量,该区间的区间和(有多少cells),该区间内某个叶子节点的最大值。
因为翻倍操作后,数字仍然是连续的,虽然输入的区间是线段树改变后的区间(线段树翻倍后节点会增多,树会变大),但是可以通过sum[rt]求出对应的原始区间。
1,2,3,4,5 翻倍后变为 1,2,3,4,5_1,5_2,如果查询的区间是[5,6],那么对于5,根据sum[rt]直接在左or右子区间递归求解即可,直到找到叶子节点为止。要注意右子......
阅读全文