以（最多 2）个 1 的连续块为行的二进制矩阵，计算其平方的迹
Binary matrix with (max 2) contiguous blocks of 1's as rows, calculate trace of its square
设 A 为一个 nxn 二进制矩阵，其行的形式为 0^k 1^l 0^m 或 1^k 0^l 1^m。此外，A 沿对角线有零。维度 n 最大可达 10^5。矩阵将通过给出 1 的块开始和结束的索引来给出。
换句话说，这些行是 1 中的 运行 被 0 包围，或者 运行 中的 0被 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)时间以下）？
这相当于求A的特征多项式的第(n-2)次系数，记为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 施加了一些进一步的限制，这可能有助于计算（？）
这可以在 O(n log n) 时间内完成 sweep-line algorithm using a Fenwick tree。
该算法按顺序计算产品对角线的条目。它维护一个包含当前列的 Fenwick 树。 Fenwick 树可以在 O(log n) 时间内更新条目并在 O(log n) 时间内报告子数组和。对于位置 {i} × {j…j'-1} 中的每个部分行，我们创建两个事件，(j, i, +1) 和 (j', i, -1)。按事件的第一个条目（列 a.k.a.time）对事件进行排序和分组。事件 (j, i, Δ) 表示在时间 j，将条目 i 增加 Δ。要计算对角线元素索引 k，首先应用时间为 k 的所有事件，然后报告相应行中所有事件的间隔，然后将它们相加。
设 A 为一个 nxn 二进制矩阵，其行的形式为 0^k 1^l 0^m 或 1^k 0^l 1^m。此外，A 沿对角线有零。维度 n 最大可达 10^5。矩阵将通过给出 1 的块开始和结束的索引来给出。
换句话说，这些行是 1 中的 运行 被 0 包围，或者 运行 中的 0被 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)时间以下）？
这相当于求A的特征多项式的第(n-2)次系数，记为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 施加了一些进一步的限制，这可能有助于计算（？）
这可以在 O(n log n) 时间内完成 sweep-line algorithm using a Fenwick tree。
该算法按顺序计算产品对角线的条目。它维护一个包含当前列的 Fenwick 树。 Fenwick 树可以在 O(log n) 时间内更新条目并在 O(log n) 时间内报告子数组和。对于位置 {i} × {j…j'-1} 中的每个部分行，我们创建两个事件，(j, i, +1) 和 (j', i, -1)。按事件的第一个条目（列 a.k.a.time）对事件进行排序和分组。事件 (j, i, Δ) 表示在时间 j，将条目 i 增加 Δ。要计算对角线元素索引 k，首先应用时间为 k 的所有事件，然后报告相应行中所有事件的间隔，然后将它们相加。