algorithm - 以 (max 2) 个连续 block 为 1 的二进制矩阵作为行，计算其平方的迹线

Question

让 A成为 nxn其行的形式为 0^k 1^l 0^m 的二进制矩阵或 1^k 0^l 1^m .另外，A沿对角线有零。维度 n 可以达到 10^5 .矩阵将通过给出 1 的块的索引来给出。的开始和结束。

换句话说，这些行是 1 的运行被 0 包围的或运行 0被 1 包围的。一行可以全为零，但不能全为 1(对角线上的零)。

一个例子 A :

[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

如何计算 A^2 的迹线高效 (根据 O(n^2) 时间)？

这相当于找到了 (n-2) 'A的特征多项式的nd系数，记为 g_2(A) ， 自从

tr(A^2) = (tr A)^2 - 2g_2(A) = -2g_2(A)

这个问题的一点点来自:

我们得到了数字 [1..n] 的排列 p 并且对数量感兴趣

r(p) = #{k | p^{-1}[k+1] < p^{-1}[k]}

这里 p^{-1}[k]表示 k 的索引在 p .我们想要计算将 r 减少 2 的两个元素的所有交换。这可以通过考虑每个索引 k 来完成。哪里 p[k]移动是有利可图的。这取决于 p[k]-1的位置和 p[k]+1 (仅在其他边缘情况下)，这就是行的形式的来源。但另一个元素的移动也应该是有利可图的，因此问题变成矩阵 A 中有多少个元素两者都有 A[i][j]和 A[j][i]等于 1我们正在统计 A^2的踪迹。 .此外，在原始问题中，我们想从中减去相邻数字对 (|p[i]-p[j]|==1) ，因为这不会减少 r由 2 但仅由 1. 但这可以在线性时间内完成，为简单起见，此问题不考虑。虽然，原始问题可能对矩阵 A 施加了一些进一步的限制。这可以帮助计算(？)

Answer 1

这可以用 sweep-line algorithm 在 O(n log n) 时间内完成使用 Fenwick tree .

该算法按顺序计算产品对角线的条目。它维护着一个包含当前列的 Fenwick 树。 Fenwick 树可以在 O(log n) 时间内更新条目并在 O(log n) 时间内报告子数组总和。对于位置 {i} × {j…j'-1} 中的每一行部分，我们创建两个事件，(j, i, +1) 和 (j', i, -1)。按事件的第一个条目(列，又名时间)对事件进行排序和分组。事件 (j, i, Δ) 表示在时间 j，将条目 i 增加 Δ。要计算对角元素索引 k，首先应用时间为 k 的所有事件，然后报告相应行中的所有事件间隔，并将它们相加。