杂知识点小记 | Sevenki's Blog

Xor Shift

是一种有用的哈希、随机算法。

ull shift(ull x){
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}

以上算法的周期是 $2^{64} - 1$ 。特别要注意的是，上面的常数 $13, 7, 17$ 并非可以随意选取。

xor shift 的本质是执行 01 矩阵向量积，具体的矩阵依上述常数决定。

为了使该随机算法表现良好，移位导出的矩阵必须可逆。

有若干对常数 $(a, b, c)$ 有比较好的性质，故我们在 xor shift 中选用它们。

另外，还可以对该算法进行一点【加密】：

ull mask = 1145141919810;
ull shift(ull x){
	x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

mask 不会影响 xor shift 的周期。

给定二维平面上的若干点 $(x, y)$ ，将它们连接成一棵树，使得 $x$ 满足 BST 的性质，而 $y$ 满足堆的性质。

构造方法：维护最右链。

OI 中很多时候， $x$ 都指代数组下标。

应用：很经典的最大子矩阵题，可以通过笛卡尔树的结构解决。（考虑子树内下标连续，且值不小于子树根）

轮流划分每个维度，设等待划分的点集为 $S$ 。

一般维护子树内所有点各维度坐标最大值最小值，然后查询直接查就行了。

修改可以使用根号重构， $O (\sqrt{n \log n})$ 重构一次。

或者二进制分组，维护若干棵 size 为 $2^{i}$ 的树。

每次加点之后，暴力从小到大合并直到不能并，类似于二进制加法。