树链剖分 + 线段树.
先写一个树链剖分.
再用线段树维护信息,每个区间需要维护最大值,最小值,前面某个数减后面某个数的最大值,最小值.
修改操作比较简单,对于询问操作,先用分割出的线段树区间的最值更新答案,再将所有分割出的区间按照经过的顺序排序,暴力枚举两个区间,用前一个区间的最小值减去后一个区间的最大值更新答案.
在线段树上处理时,需要注意移动的方向.
1 | //%std |
夢はここに 思い出は遠くに
树链剖分 + 线段树.
先写一个树链剖分.
再用线段树维护信息,每个区间需要维护最大值,最小值,前面某个数减后面某个数的最大值,最小值.
修改操作比较简单,对于询问操作,先用分割出的线段树区间的最值更新答案,再将所有分割出的区间按照经过的顺序排序,暴力枚举两个区间,用前一个区间的最小值减去后一个区间的最大值更新答案.
在线段树上处理时,需要注意移动的方向.
1 | //%std |