树上分块。

第一种是随机撒点，在树上随机撒 $\frac{n}{S}$ 个点，关键点间期望距离不超过 $S$。优势很明显，当 $S$ 取根号的时候，可以处理出所有关键点间的信息，然后跳根号次就可以跳出一条路径。这个做题的方法很可洞见。

第二种是王室联邦式分块，方法是，在 dfs 过程中将子树大小能够划到一块的就划，设 $S$ 为阈值，则每块大小为 $[S, 3S]$，块个数 $\frac{n}{S}$ 左右。优势是每个点最近的为关键点的祖先的距离为 $O(S)$。这个做题的方法也是处理出关键点的信息，然后将询问拆成 $x \rightarrow a \rightarrow b \rightarrow y$，其中 $a$，$b$ 分别是 $x$，$y$ 的最近关键点祖先。

第三种是 top cluster，我显然不会。

我不是电子越共，而且这个东西也不小众。

Mistakes That I Don't Want to Make Once Again.

// Caution //

1. 差分 / 前缀和后注意询问区间端点有变化……
2. 不要考虑了右边界就不考虑左边界

// Caution //

1. 只减不加莫队如果维护了数据结构, 换块的时候要将前缀块 (处理过的) 的影响消除. 一个高庙的写法是开个 stack 记录修改, 然后将换块的左指针挪动的 stack 清了. at - rrads
2. 只加不减应该也有类似的问题.

// Caution //

李超树动态开点时，当前结点为空应该直接赋值后退出，即：

int upd(int id, int u, int l = -vinf, int r = vinf) {
    if (!u) return tr[u = ++tid] = id, u;

// Caution //

决策单调性的题目，如果贡献与之前的 dp 值有关，就不能写整体二分了，不然会出现「第一个求的是 dp[mid]」这样转移顺序的问题，比如诗人小狗。

莫队的重学。

普通莫队的排序有很多讲究，以后只写回滚莫队好了，至少复杂度是稳定的。这是莫队的排序关键字：$(\textit{bel}_{ \text{left endpoint }}, \text{ right endpoint})$。

回滚莫队和莫队还是有点区别的，具体而言就是对序列分块，块内询问暴力，跨块询问就根据左端点所在的块分类，将左端点在一个块内的询问拉出来，按照右端点排序，这样移动右端点就是单调的，而左端点每次从（所在）块的右端点 $+1$ 的位置开始暴力跑，平衡了复杂度。

上面说的是只加不减莫队，只减不加莫队和这个有点区别。

首先还是按左端点所在块分类，然后右端点按降序排，莫队维护的区间右端点就从序列末端往前单调地跑就行了。只减不加莫队的区别在于，块内询问我们不必暴力了，直接跟着跑就行了。

举个例子，$\texttt{[}\texttt{(}_1\texttt{)}_1\texttt{(}_2\texttt{)}_2\texttt{]}$（方括号代表一个块，角标用以区分不同询问），如果是只加不减莫队的话，维护的右指针根本跑不到块内（从右端点开始单调向右跑），而只减不加莫队的右指针可以跑进来。注意两种莫队的左端点都是暴力的，所以不需要考虑。

高维莫队真的很没意思，就是强行加了一维时间轴，排序的方法是：

if (bel[x.l] != bel[y.l]) return x.l < y.l;
else if (bel[x.r] != bel[y.r]) return x.r < y.r;
return x.tim < y.tim;

如果有什么厉害的排序 trick 或其他 trick 或高庙题记得放上来。

link。

考虑把原问题写成一个在 $\left(\log_2 \max v \right) \times n$ 的矩阵里选出三列，我们首先预处理出 $j \cap q$。具体，我们需要对于每一个权值 $v$ 求出一个最大的下标 $p$（$1 \leqslant p \leqslant n$）满足存在极大的 $q < p$ 且 $v \cap a_p \cap a_q = v$，即 $v \subseteq \left(a_p \cap a_q\right)$，这个可以做一个二元组 dp，即设 $f_v$ 为对于 $v$ 而言的答案，注意到 $p$ 和 $q$ 的实际意义是「满足左右两边存在有一个位置做并操作后是 $v$ 的超集的位置下标」的最大值和次大值，所以更新答案是容易的。

考虑如何转移。对于一个左闭右开区间 $[0, 2^n)$，我们分治求出 $[0, 2^{n-1})$ 和 $[2^{n-1}, 2^n)$ 的 dp，当然左边区间的 dp 值不会对右边区间产生影响，所以我们考虑右边区间对左边区间的影响。$\forall i \in [l, m)$，我们需要从 $i$ 的超集转移到 $i$，因为在 dp 时我们实际上是把所有贡献放到一个点上，又注意到 $i-l+m$ 和 $i$ 的关系就是二进制意义下多了一个最高位的 $1$，所以只需要从 $i-l+m$ 转移到 $i$ 即可（有点谜语，但就这样吧）。

然后就贪心取最高位，挨个取 max 就行了。

int n, a[1000100], qwq;
pii dp[3000100];
pii upd(const pii& x, const pii& y) {
    if (x.first > y.first) {
        return pii(x.first, max(y.first, x.second));
    }
    else {
        return pii(y.first, max(x.first, y.second));
    }
}
void sos_dp(int l, int r) {
    if (r-l == 1) {
        return;
    }
    int mid = (l+r)/2;
    sos_dp(l, mid), sos_dp(mid, r);
    for (int i=l; i<mid; ++i) {
        dp[i] = upd(dp[i], dp[i-l+mid]);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
        dp[a[i]] = upd(dp[a[i]], pii(i, 0));
    }
    qwq = 1;
    for (int up=*max_element(a+1, a+n+1); (1<<qwq) <= up;) {
        qwq++;
    }
    sos_dp(0, 1<<qwq);
    int ans = 0;
    for (int i=1; i<=n; ++i) {
        int offset = 0;
        bool f = 0;
        for (int j=qwq; j>=0; --j) {
            if (~(a[i]>>j)&1 && dp[offset|(1<<j)].second > i) {
                offset |= 1<<j, f = 1;
            }
        }
        if (dp[offset].second > i) {
            f = 1;
        }
        if (f) {
            cmax(ans, a[i]|offset);
        }
    }
    cout << ans << "\n";
}

重新学了一遍记忆化搜索实现的数位 dp，谈一下理解，毕竟我是普及组小朋友。

这个东西的实际意义大概就是通过将「有上界限制的分支使用搜索实现，一般的分支使用 dp 转移」的手法，将带有上界限制的数位计数问题一般化为所有数位都可以任意取的计数问题。

拜托，存数位请一定不要将 num[1] 置为最高位！比如 $1000$、$100$，两个数在指针相等时所指的数位不一样。果然还是要看 DJ 的！