对空间为 N sqrt N 的分块的卡常建议

当然我不是专业的，下面的内容不保证一定有道理，仅供参考。

首先可以尝试调整数组的维度，把循环中不变的放在前面。

接下来，如果前面的维度不变了（循环中每次都不变，或者多次访问中不变），可以用指针存下来，以后访问指针。我就用这个方法在 UOJ 上卡过了。

举几个例子（ui 为 unsigned int。不必理解变量名，理解原理就行了）：

散块内部（循环中每次都不变）：

CPP

ui bid = pos[l];
Block& b = block[bid];
ui b_l = bl[bid], rk_d_1 = b.rk[d - 1];
ui* b_les_l_b_l = b.les[l - b_l];
FOR(i, l, r) {
    if (d <= a[i] && a[i] <= u) {
        ans += b.les[i - b_l][b.rk[a[i]]] - b.les[i - b_l][rk_d_1] -
               b.les[l - b_l][b.rk[a[i]]] + b.les[l - b_l][rk_d_1];
    }
}

式子的后面两项中，每次都是 b.les[l - b_l][...][...]，因此可以改成：

CPP

            ui* ptr = b.les[l - b_l];
            FOR(i, l, r) {
                if (d <= a[i] && a[i] <= u) {
                    ans += b.les[i - b_l][b.rk[a[i]]] - b.les[i - b_l][rk_d_1] -
                           ptr[b.rk[a[i]]] + ptr[rk_d_1];
                }
            }

整块之间（多次访问中不变）

其中有一部分式子长这样：

CPP

ctb[j][j - 1][b.rk[u]] - ctb[j][j - 1][b.rk[d - 1]] -
ctb[j][l - 1][b.rk[u]] + ctb[j][l - 1][b.rk[d - 1]] - /* 另一坨式子 */

这里虽然 j 是循环变量，但是每次都有 ctb[j]，因此可以把 ctb[j] 存起来：

CPP

ui (*ptr)[MAXBLEN] = ctb[j]; // MAXBLEN 是数组第 3 维的大小

ptr[j - 1][b.rk[u]] - ptr[j - 1][b.rk[d - 1]] -
ptr[l - 1][b.rk[u]] + ptr[l - 1][b.rk[d - 1]] - /* 另一坨式子 */

对空间为 N sqrt N 的分块的卡常建议

讨论操作

回复

相关推荐

对空间为 N sqrt N 的分块的卡常建议