请教一个算法问题

[luoluoluo]

对于数组A，B：
A = [a0, a1, ... , an-1]
B = [b1, b2, ..., bn-1]
有多少组i, j使得：
i < j && A[i] < B[j]

[em70]

A,B数组长度相等吗

[luoluoluo]

@em70 等长，这个影响解法吗？

[wisatbff]

先排序，然后就不用说了吧

[freetg]

k=0
for i in xrange(n-1):
for j in xrange(i+1, n-1):
if A[i] < B[j]:
k += 1
print k

[luoluoluo]

@wisatbff 在下愚钝，请详述
@freetg 这个解法太过暴力

[yangff]

树状数组

[wisatbff]

@luoluoluo 排序之后和归并排序的“归并”操作类似

[em70]

遍历肯定可以解决,算法复杂度2^n,主要你希望简化到多少?

[takato]

O(nlogn)

[luoluoluo]

@yangff 数组数组是指数组区间维护最小值，查询的时候变快了，O(nlog(n))吗？

@wisatbff 是说按照数组值排序，再顺序往下归并，在依次比较下标吗？（如果我理解错了请说的在详细点，谢了哈）可是对于每个A的下标，B中可能存在不止一个下标符合，这样最坏的情形是不是O(n^2)

@em70 我希望可以降到O(n)

[bcxx]

@luoluoluo 试试可以将两个数组进行基排（或者其他 O(n) 的排序算法），然后再遍历两个数组，用类似归并排序的方法来逐个比较就可以了。这样就 O(n) 吧

[xjx0524]

两个数组分别排序O(nlog(n))
遍历A数组，对其中每个元素在B中二分，可以知道有多少比他大的
这样时间复杂度O(nlog(n))

[bcxx]

@bcxx 诶这里还说错了，应该是 O(n+k) 之类的排序算法……

[xjx0524]

@bcxx 仔细想了下，排序完之后可以O(n)统计结果，那样瓶颈就在排序了

[GtDzx]

线段树或者树状数组 复杂度O(nlogn)
元素取值范围足够大的话，应该不存在O(n)算法。否则可以通过构造这类问题来O(n)解决n个元素排序问题。(这点我没想太仔细，不过感觉是上可以这样证明复杂度下限的 :P）

[luoluoluo]

@xjx0524 下标考虑了吗？

@bcxx 归并的话如我上面所说，如果B里面的数都大于A，最坏的情况是O(n^2)吧

[xjx0524]

@luoluoluo 和下标有什么关系？

归并那种方法，如果B里面的数都大于A，最坏的情况是O(2n)，省略常数就是O(n)

[luoluoluo]

@xjx0524
i<j && A[i]<B[i] 共有多少组组合满足，怎么和下标没关系呢？ i < j

[xjx0524]

@luoluoluo
我说的那种二分的方法，假设n为B数组元素个数
遍历A数组，拿a[i]在B中二分，找到位置使b[j]<=a[i]且b[j+1]>a[i]，那么总结果就加上n-j-1(如果数组索引从0开始)
对A数组中每个元素都这么做时间复杂度O(nlogn)

[glasslion]

keyword: 逆序数