11.15 联测

A

先找找有什么通解。发现找不太到。

考虑直接构造，每个点 $i$ 向 $i-lowbit(i)$ 连边。

容易发现会有大约 $\log n$ 个点的 $i-lowbit(i)<l$。也就是有若干个连通块。

考虑暴力对这些点跑 kruscal，复杂度 $O(q\log^2n\log\log^2n)$。

打表发现跑出来的生成树一定满足 $l$ 向其他点连边，复杂度将为 $q\log n$。

B

直接朴素 dp，$O(n^2)$。

数据结构优化，线段树上 $tr_j$ 表示下一个区间选了 $[j,i]$ 的贡献。

若 $[j,i]$ 非法，$tr_j=0$。反之 $tr_j=f_j$。

维护两颗线段树，表示重要位置在奇/偶数下标。

• 如果 $i$ 不是重要节点，那么 $j\in[1,lst_i]$ 不能选。

• 如果 $i$ 是重要节点，那么 $j\in [1,pre_{i,1-o}] \cup [pre_{i,o}+1,i]$ 不能选。

  注意撤销 $[pre_{pre_{i,o},o}+1,pre_{i,o}]$ 的标记。

扫一遍 $i$ 的同时将 $f_i$ 加进线段树即可。