CSCI3160 Special 2：逆序对输出、支配归约与矩阵分块

原件：Sp02 题目（本地课件） p.1；原 PDF 标题误作 CSCI3610。 每题先题解后解析；所有题解独立推导，不是官方答案。

Problem 1：输出全部逆序对

题解

给每个元素保留原下标，执行归并分治。合并两份有序列表时，若右元素小于当前左元素，它就与所有剩余左元素构成逆序，逐对输出原下标。时间O(n log n+k)，比题目要求O(n log² n+k)更强。

具体解析

按原位置中点划分，跨区对天然满足左下标小于右下标；左、右递归分别输出内部逆序。合并时若R[j]<L[i]，有序性使剩下L[i..]全部大于R[j]，输出这些对后取走R[j]。若相等则先取左，不输出，保持严格逆序定义。

每个逆序对只在它的两端首次被递归分到左右的那层输出一次。除实际输出外，每层归并O(n)，共O(log n)层；实际输出一共k对，工作O(k)。不能仅写“每个右元素遍历全部左元素”而不利用已排除的小元素，否则会多做不对应输出的平方工作。

自取[3,1,2]，输出原位置(1,2)、(1,3)。排序后的元素位置变了，若不保留原下标，会把值对或新位置错当作原题逆序。输出可流式写出，除输出外缓冲区O(n)。

输出成本必须按条支付。 在补充数组 [4,3,2,1] 中，输出下标对为 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)，共 6 条。一般严格降序数组有 $k=n(n-1)/2$ 条，单是把这些对写出就需要 $\Omega(k)$ 时间。因此 $O(n\log n+k)$ 同时区分了排序管理成本和不可省掉的输出成本；只问总数时，一个整数就能代表这 $k$ 条，才可以做到 $O(n\log n)$。

Problem 2：用二维支配计数求逆序数

题解

若元素互异，可映射为Pᵢ=(i,−A[i])，每点支配的先前点数之和就是逆序数。为兼容整数重复值且支配采用非严格≤，用更稳妥的编码

构造与最后求和O(n)，调用黑盒一次f(n)，总f(n)+O(n)。

具体解析

按课程定义，Pⱼ支配Pᵢ需要i≤j且第二坐标也≤；排除自身后就是i<j。第二坐标条件化为 $(n+1)(A[i]-A[j])\ge j-i$。若A[i]>A[j]，整数差至少1，左侧≥n+1而右侧≤n−1，成立；若相等或更小，左侧≤0而右侧>0，不成立。因此恰好对应严格逆序，等值不误计。

自取[2,2,1]、n=3，映射点为(1,−9)、(2,−10)、(3,−7)。第二个点不支配第一个，第三个支配前两个，计数0、0、2，总逆序2。黑盒若包括自身，需从每个结果减1；课程定义支配两个不同点，因此原接口已排除自身。坐标运算按课程字长模型或常数个字保存。

Problem 3：宽矩阵乘法

题解

把m×n矩阵按行分成ceil(m/n)块n×n，把n×m矩阵按列分成相同数量的n×n块，不足的补零。每个输出块是一对n阶矩阵乘积，共ceil(m/n)²对；用Strassen得到O(m²n^0.81)。

具体解析

这里中间公共维度就是n，所以一个输出块不需要再对多个中间块求和。m≥n使ceil(m/n)≤2m/n，故乘法总工作≤常数·(m/n)²n^2.81。填充、读入及输出O(m²+mn)，因n≥1而不超过主界。

自取m=5,n=2：把第一矩阵分3块两行，第二矩阵分3块两列，最后边缘补到6；需9次2阶乘法，结果从6×6裁回5×5。n非二次幂时再按Regular2 Q5补到不足2n，仍只改变常数。

Problem 4：一般长方矩阵乘法

题解

对m×n乘n×t，m≥n≥t，以t为块边长。第一矩阵分成ceil(m/t)×ceil(n/t)块，第二矩阵分成ceil(n/t)×1块。每个输出块累加对应中间块乘积，总块乘法次数O(mn/t²)，各花O(t^2.81)，总O(mnt^0.81)。

具体解析

与Q3不同，公共维度n现在被切开，所以需要求和：输出第i块是所有j的AᵢⱼBⱼ之和。每次累加t²个元素，合计O(mn)，不超过乘法界；输入与输出大小也不超过O(mn)，因为t≤n≤m。

自取m=6,n=4,t=2：A分3×2块，B分2×1块，每个输出块加两个2阶乘积，总6次乘法和3次块加法，输出6×2。把它错写成只有3次乘法，会漏掉中间维度的贡献。

Problem 5：k个有序数组的合并

题解

将每个非空数组的首元素与其数组编号、位置放入最小堆。反复取最小者输出，再把它所在数组的下一个元素加入。堆中至多k个元素，每个输出需O(log k)，合计O(k+n log k)；所有k个数组非空时k≤n，通常写O(n log k)。

具体解析

不变量：堆里恰好保存每个尚未耗尽数组的最小未输出元素。全局最小未输出值必在这k个候选中，因此每一步取堆顶都保持输出有序。不同长度只会让部分数组更早耗尽，不需要填补虚假元素。

自取[1,7]、[2,4,9]、[3]：堆初始1、2、3；输出1补7，输出2补4，输出3不补；继续4、7、9。每个元素进堆出堆各一次，堆空间O(k)，输出另计O(n)。k=1时直接复制O(n)，严格统一可写O(k+n log(k+1))。若允许任意多空数组，读取k个数组描述本身需O(k)，不能无条件省掉这个初始化项。

来源与证据

题目p.1，以上为自行推导；给出了比要求更强的Q1界以及Q2重复值的严格处理。