能否使用线段树维护动态的逆序对并且复杂度比 O(mnlogn)O(mnlogn)O(mnlogn) 优?其中 nnn 表示数据的个数。
意思大概是这样的:
有一个长度为 nnn 的序列,现在要对其操作 mmm 次,每次的操作是 222 种方式中的一种:
方式 111,111 lll rrr kkk,表示将 lll ~ rrr 之间的数字每个加上 kkk。
方式 222,222,表示查询现在整个数列的逆序对个数。