对于操作一,用平衡树删除第 小的数,并获取他在线段树所对应的下标 ,然后插入 ,将线段树上第 个元素更改为 。
对于操作二,用区间线段树维护区间最大值与区间最小值的差即可。
时间复杂度约为 。
主要难点就在于(其实也不难)将修改操作转化为删除与插入操作,并且平衡树上不光需要存值,还需要存下标。
注意要开 long long。
long long