站外题求助
  • 板块灌水区
  • 楼主never_AK
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/21 14:20
  • 上次更新2024/7/21 15:34:28
查看原帖
站外题求助
373757
never_AK楼主2024/7/21 14:20

打模拟赛遇到的,题目如下:

数据范围:

时间限制:500ms

题解给了一个O(nlog2n)O(n log^2 n)的做法

但是我有一个奇怪的想法:

开一颗线段树维护区间最大值,由于修改的特殊性:

当且仅当一段区间的(max == 修改的x)时,max++

否则直接忽略(最大值肯定不变)

加上lazytag

这样子能不能做到O(nlogn)O(nlogn)呢

2024/7/21 14:20
加载中...