上午比赛

好险，还好第一题AC了，不然就0分了，又是没有爆零的一天

下午树状数组

下午学习了新的数据结构——树状数组，比昨天线段树的代码量明显降低了不少，而且它可以实现线段树的功能，并且比线段树的时空复杂度都更优，唯一的缺点是转化的思维量较大，比较费脑子
然后打了两道模板题

树状数组2这题用到了差分的思想，将原本的树状数组求前缀和变成了求第x位置元素

上午比赛AC了，看到题目第一眼就想到背包，但后面一想，传统背包做的是求最大值，而这题要求最小值，那么，我们可以存储相反数，将其从最小值问题转为最大值，这样背包模板就可以套了，记得滚动数组优化

这题考虑到区间只有三种可能：包含、相交、分离
那么只考虑相交与分离的情况进行动规

注意到，当两个区间包含时，必然是长度更长的区间中有长度较小的区间

所以要特别判断一下当存在包含关系时，是要将子区间先单独抽离在抽离整个大区间，还是整个大区间直接抽离所得的分数更高

这样的话我们可以先求解对于每个数所构成的区间，用二元组存储，然后根据长度的不同，进行排序，这样枚举时，只要枚举小于当前区间长度的区间，判断其是否属于当前区间的子区间即可

状转方程早上打比赛的时候没有想到，前面的部分想到了，比较可惜没有打出来