题解：P10690 Fotile 模拟赛 L

· · 题解

更劣的复杂度！大常数 O(N^2 + NM)。

现在我们已经求得 a 的前缀异或和，题意转化成选择 [l - 1, r] 中两个数使其异或最大。

首先这个 N, M 很小啊，但是直接暴力 O(MN^2) 肯定过不去。
但是这是分块的练习题啊，如果用分块（块长取 O(\sqrt{N})）优化暴力就可以 O(M (\sqrt N)^2) 卡过去了。

具体的，我们求一个 mx_{i, j} 表示左端点位于第 i 个块，右端点位于第 j 个块的最大异或值，求一个 val_{i, j} 表示 i 与第 j 个块中的数异或得到的最大异或值。
这里直接这么求：

// #define rep(i, a, b) for (int i = (a); i <= (b); ++i)
rep(i, 1, n) rep(j, i, n)
    chkmax(mx[bel[i]][bel[j]], a[i] ^ a[j]),
    chkmax(val[i][bel[j]], a[i] ^ a[j]),
    chkmax(val[j][bel[i]], a[i] ^ a[j]);

然后询问的时候我们分别查区间内的整块与整块、散块与整块、散块与散块的最大值，每部分都是 O((\sqrt{N})^2)。

代码：

LL qry(int l, int r) {
    LL res = 0;
    if (bel[l] == bel[r]) {
        rep(i, l, r) rep(j, i, r)
            chkmax(res, a[i] ^ a[j]);
    } else {
        rep(i, bel[l] + 1, bel[r] - 1) rep(j, i, bel[r] - 1)
            chkmax(res, mx[i][j]);

        rep(i, l, bR[bel[l]]) rep(j, bel[l] + 1, bel[r] - 1)
            chkmax(res, val[i][j]);
        rep(i, bL[bel[r]], r) rep(j, bel[l] + 1, bel[r] - 1)
            chkmax(res, val[i][j]);

        rep(i, l, bR[bel[l]]) rep(j, i, bR[bel[l]])
            chkmax(res, a[i] ^ a[j]);
        rep(i, bL[bel[r]], r) rep(j, i, r)
            chkmax(res, a[i] ^ a[j]);
        rep(i, l, bR[bel[l]]) rep(j, bL[bel[r]], r)
            chkmax(res, a[i] ^ a[j]);
    }
    return res;
}

复杂度不是很优，但是优点是真的暴力，好想。

Code 或者 Code