1. 题目

传送门= ̄ω ̄=

2. 题解

树链剖分模板题。
先剖树成链,再用线段树维护一条一条的链。
线段树连懒惰标记都不用,单点修改

代码: