day5下午

清北学堂--刷题班

题解

t1

t2

and值满足只会减小或者不变，
or的值满足只会增减或者不变
所以暴力60分的做法，枚举左端点，往右走，不满足了退出
正解，二分，满足单调性，那么二分一个位置，判断是否可以满足，st表O(1)查询。
st表记录以每个节点往后$2^i$方个的& | 值，有重复的没关系（重点），重复的，多& |一遍对结果没有影响，

t3

树
确定一个子树不选时，它的贡献一直都是 2^子树大小
树形dp+01背包，
f[i][j]以i为根的树中，拿j个果子的方案数，
首先拿自己的果子，有k个果子在子树里