计算范围内的反转
我参加了一个编程比赛，我无法解决问题，问题是：
给定一个n个整数的数组A，我需要计算给定范围内求逆的次数。提供一个整数m，它表示范围的数量，然后是m行，在每一行中给出两个整数li和ri。
我们必须只计算指定范围内的反转，即从li到ri(包括0)的反转(基于0的索引)。
如果 A[i] 两个元素 A[i] 和 A[j] 添加到反演中
例如:< code>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），这肯定是不可接受的，因为时间限制是1秒。
共有3个答案
这里是对之前答案的详细阐述，也填补了潜在的空白。首先，在O(n log n)时间内计算并存储数组所有前缀的求逆次数，方法是从右到左一次添加一个元素，并进行二叉查找树搜索，在所有先前元素的树中找到该元素，以确定添加的额外求逆次数，然后将该元素插入到二叉树中(并将该树作为自平衡二叉查找树来维护)。然后你同样计算和存储所有后缀中的倒置数。然后，如果您想计算范围[L，R]中的求逆次数，您可以将以L开头的前缀的求逆次数与以R结尾的后缀的求逆次数相加，然后减去整个数组的求逆次数。这几乎给出了答案，但并不完全，因为它给出的是答案减去范围[1，L-1]和[R 1，n]之间的求逆次数。所以你需要能够计算数组中任意前缀和后缀对之间的逆序数。为此，您需要计算任意前缀和以sqrt(n)的倍数开头的特定后缀之间的倒序次数。你可以在o(n^(3/2 log n时间中这样做，对每个后缀进行排序，然后，对每个后缀，从左到右给前缀添加一个元素，在后缀中做一个二分搜索法，以计算出要给倒置的次数增加多少。类似地，您计算并存储以sqrt(n)的倍数结尾的每个前缀与前缀右侧的每个元素之间在o(n^(3/2 log n时间内的求逆次数。
然后，对于给定的范围，取前缀和后缀并将后缀四舍五入，以sqrt（n）的最接近倍数结尾，并在O（1）时间内查找倒置次数。然后取后缀中的剩余元素，并在O（sqrt（n））时间内查找前缀中以sqrt（n）的最接近倍数结尾的倒置次数。然后取后缀中的剩余元素和前缀中的剩余元素（不包含在sqrt（n）endpoint中），并蛮力计算它们之间的倒置次数在O（sqrt（n）log n）时间内。每个范围的总计算时间为O（sqrt（n）log n），给出O（（m n）sqrt（n）log n）时间的总体运行时间，应满足1秒的时间限制。
O（（n m）*sqrt（n）*log（n））时间，O（n m）空间离线查询算法（必须提前知道所有查询范围）：
- 将数组A分成大约sqrt（n）相等的部分。
- 对数组的每个部分执行步骤3...7。
- 初始化3个指针（
普贝因、Pmid、Pend），使它们都指向数组当前部分的末尾（甚至更好地指向属于该部分的范围的最右边开始）。 - Advance
Pend；更新订单统计树，确定Pmid和Pend之间的反转次数；当Pend与数组当前部分开始的某个范围的末尾一致时，执行步骤5...7。 - 向后移动
普贝因，直到它与第4步中找到的范围的开头一致。在order-统计树中累积的元素数小于普贝因指向的值（但不更新树）。 - 查找
Pstart和Pmid之间的倒置次数（使用合并排序或单独的订单统计树）。 - 将步骤4、5、6中找到的倒置数相加。这是当前范围的倒置数。
这里可以使用比特/分域树作为顺序统计树的有效实现。在这种情况下，需要进行一些预处理:用数组排序副本中的索引替换数组值，以压缩值的范围。
O((n m) * sqrt(n))时间，O(n * sqrt(n))空间的在线查询算法。正如大卫.艾森斯塔特所暗示的。
预处理：
- 用数组排序副本中的索引替换数组值以压缩值范围。
- 将数组A分成大约sqrt（n）相等的部分。
- 对于数组的每个部分
B执行步骤4...8。 - 零初始化大小为“n”的位集。切换与“B”部分值对应的位。对于此位集，计算前缀和
P数组和后缀和S数组。 - 对于每个部分
C前面的部分B执行步骤6。 - 从
C部分的最后一个值v开始向后，将所有值P[v]相加并将sqrt（n）结果写入查找表E。此步骤的复杂性为O（n*sqrt（n））。 - 对于每个部分
D以下部分B执行步骤8。 - 从
D部分的第一个值v开始向前，将所有值S[v]相加并将sqrt（n）结果写入查找表F。此步骤的复杂性为O（n*sqrt（n））。 - 使用增量算法（Fenwick树）计算所有块后缀中的倒置次数（所有从块边界开始且长度不大于
sqrt（n）的子数组）。将结果写入查找表G。此步骤的复杂性为O（n*log n）。 - 使用增量算法计算所有块前缀中的反转次数。将结果写入查找表
H。此步骤的复杂性为O（n*log n）。 - 使用
E或F中的任何一个以及G或H中的任何一个来计算连续块中的反转数（任何一对块用于开始和结束位置）。将结果写入查找表R。此步骤的复杂性为O（n）。
经过预处理后，我们得到了几个LUT，其中包含块前缀/后缀（G、H和O（n）空间）中的反转数、完整块和块前缀/前缀/后缀之间的反转数（E、F、O（n*sqrt（n））和连续块中的反转数目（/RO（n））空间）。（可选地，我们可以将E和F与R，这增加了预处理时间，但为第一个查询步骤提供了O（1）时间）。
查询：
- 使用
R获得连续完整块中的反转数，使用E、F在前缀/后缀和每个完整块之间添加反转数，用G和H添加前缀和后缀中的反转数目 - 要获得前缀和后缀之间的倒数，请使用基数排序（
sqrt（n）计数器、2次计数过程和2次分配值过程）对两者进行排序，然后将它们合并 - 将步骤1和2中的值相加，以获得查询范围的反转数
这是一个O（（n m） sqrt n log n）时间算法。这可能还不够好，无法通过，但这里似乎有些不太对劲 - 通常的编程比赛技巧不起作用。（O（（n m） sqrt n） 可能更小心地实现。
将输入数组划分为长度为sqrt n的sqrt n子数组，称为块。使用用于计数反演的增量算法，对于由块和数组前缀组成的每对，计算第一个元素来自前者，第二个元素来自后者的反演数。（O（n sqrt n log n））对前缀块对执行相同的操作。
对于每个输入范围，将其分解为一些块(阻塞元素)和少于2个sqrt n元素(未阻塞元素)的并集。使用预计算的结果和包含-排除，找出至少有一个元素被阻塞的范围内的求逆次数。(O(sqrt n))计算包含两个未阻塞元素的值域中求逆的次数，并将其加到这个量上。(O(sqrt n log n))
-
假设您有一个间隔列表，例如[（0 4），（1 3），（2 5），（2 6）]。此列表未排序。然后给您一个范围，如[1 5]。您必须返回适合范围内的间隔数。在这个问题中，它将返回2。（（1 3）和（2 5）） 间隔列表保持不变，但我们最多得到100000个查询，每个查询由一个范围组成。对于每个范围查询，我们必须返回适合其中的间隔数。 在研究之后，我读到了间隔树。但是，您只能查询与任何给定范围重叠的间
-
我的方法是生成所有素数直到（埃拉托色尼筛），并检查给定范围内的每个数是否可被素数的平方整除。这些数字的计数从范围的长度中减去，以给出平方自由数。 但是这种方法在复杂度上超时了，请建议一些其他的方法
-
本文向大家介绍在C ++中计算给定范围内的阶乘数，包括了在C ++中计算给定范围内的阶乘数的使用技巧和注意事项，需要的朋友参考一下 给定范围是从变量保存的整数值开始，比如说从开始直到变量结束，而任务是计算给定范围内可用的阶乘数的总数。 什么是阶乘数 数字的阶乘是通过将数字中的数字相乘，同时将数字的值减1来计算的。它由符号“！”表示 即0！，1！，2！，3！，5！，....等 0阶乘！和1！始终为1
-
问题内容： 在这里，最低年龄是10岁，因此我们首先计算范围10-15。该范围内有5个学生。对于第二个范围，我们需要找到年龄> 15（即18）。因此，第二个范围是18-23，依此类推。如果能自动计算范围并计算该范围内的数据，我将不胜感激。 问题答案： 您可以在SUM（）语句中使用条件来获取该条件所在的计数。我会计算年龄在BETWEEN（）必要范围内的条件。试试这个： 这只会返回一行，但是它将包含您需
-
本文向大家介绍计算C ++中给定范围内的最小元素数，包括了计算C ++中给定范围内的最小元素数的使用技巧和注意事项，需要的朋友参考一下 我们得到了一个大小为N的整数数组。变量L和R定义了一个介于1和N之间的范围。目标是找到位于范围L和R中的最小元素数，使得L> = 1且R <= N. 我们将遍历位于范围L和R中的元素并找到最小的元素，以实现此目的。 同样，遍历范围L和R的元素，如果任何元素等于在步
-
问题内容： 我有一个NumPy值数组。我想计算在特定范围内有多少这些值，例如x <100和x> 25。我已经读过有关计数器的信息，但它似乎仅对指定值有效，对值范围无效。我已经搜索过，但是没有发现有关我的特定问题的任何信息。如果有人可以指出适当的文档，我将不胜感激。谢谢 我已经试过了 但这只是给我25到99之间的数字。 编辑 我正在使用的数据是由另一个程序创建的。然后，我使用脚本读取数据并将其存储为