DS做题记录
BZOJ3252 攻略
贪心很简单，写法的话用长链剖分非常简单。
P11071
按位考虑很 easy，每一位开一棵线段树空间就爆了，一个离线的 trick 就是类似分块逐块处理，我们每一位用一棵线段树算出对所有询问的贡献，这样空间就是一棵线段树的空间了。
CF301D
考虑最多 \(O(nlogn)\) 对，直接二维数点即可。
CF1946F
上一个的加强版，考虑状态也是 \(O(nlogn)\) 的，只不过权值是开头是 \(l\)，结尾是 \(r\) 的子序列的数量。考虑算出这个权值我们就要 DP。
\[f_{i, j} = \sum_{a_i | a_j, a_k | a_j, a_i | a_k} f_{k, j}
\]
考虑这么枚举的复杂度为 $$\sum_i (n / i) ln(n / i) = n ln^2 n$$。
所以直接三层 for 循环预处理然后二维数点即可。