关于线段树
  • 板块学术版
  • 楼主icypenguin/ll
  • 当前回复17
  • 已保存回复17
  • 发布时间2023/6/17 18:46
  • 上次更新2023/10/23 12:55:34
查看原帖
关于线段树
751881
icypenguin/ll楼主2023/6/17 18:46

能否使用线段树维护动态的逆序对并且复杂度比 O(mnlogn)O(mnlogn) 优?其中 nn 表示数据的个数。

意思大概是这样的:

有一个长度为 nn 的序列,现在要对其操作 mm 次,每次的操作是 22 种方式中的一种:

方式 11,11 ll rr kk,表示将 ll ~ rr 之间的数字每个加上 kk。

方式 22,22,表示查询现在整个数列的逆序对个数。

2023/6/17 18:46
加载中...