algorithm - 计算范围内的反转

Question

我参加了一个编程竞赛，我无法解决一个问题，问题是:

给定一个包含 n 个整数的数组 A，我需要计算给定范围内的反转次数。提供一个整数 m 来表示范围的数量，然后是 m 行，在每行中给出两个整数 li 和 ri。

我们必须只计算指定范围内的倒置，即从 li 到 ri(包含 0 的索引)。

如果 A[i]>A[j]，两个元素 A[i] 和 A[j] 添加到反演中和 i<j .

例如:A=[3 2 1 4]

反转是:

(2, 1), (3, 1), (3, 2) i.e. total number of inversions are 3.

输入:

3 2 1 4    //Array A 
3         // m - no. of ranges
1 2      // range
2 3
0 3

输出:

1
0
3

约束:

n<=2*10^4
m<=2*10^4
A[i]<=10^9

我知道在整个数组上以 O(nlogn)(例如 BIT 或合并排序)计算倒置计数的方法，如果我在这里对每个范围应用相同的方法，复杂度将是 O(mnlogn)，这肯定是 Not Acceptable 时间限制为 1 秒。

Answer 1

这是一个时间复杂度为 O((n + m) sqrt n log n) 的算法。这可能不够好，无法通过，但这里似乎有些不对劲——通常的编程竞赛技巧不起作用。 (O((n + m) sqrt n) 可能更小心地实现。)

将输入数组分成 sqrt n 个长度为 sqrt n 的子数组，称为 block 。使用增量算法计算反转，对于由数组的 block 和前缀组成的每一对，计算第一个元素来自前者而第二个元素来自后者的反转次数。 (O(n sqrt n log n)) 对前缀 block 对执行相同的操作。

对于每个输入范围，将其分解为一些 block ( block 元素)和少于 2 sqrt n 元素(未 block 元素)的并集。使用预先计算的结果和包含排除，找到至少一个元素被阻止的范围内的反转次数。 (O(sqrt n)) 计算涉及两个未分块元素的范围内的反转次数并将其添加到该数量。 (O(sqrt n log n))