题解

思路

设被激活的点依次为 $x_1<x_2<\cdots<x_k$，再补一个权值为 $0$ 的哨兵点 $x_{k+1}=m+1$。区间 $[l,r]$ 的最右激活点恰为 $x_i$，当且仅当

$$l\le x_i\le r<x_{i+1}.$$

因此，只要知道相邻两个被选点，就能确定前一个点对答案的全部贡献。

记 $S(i,j)$ 为满足 $l\le i\le r<j$ 的区间个数，其中 $i<j$。令 $dp_j$ 表示最后选择点 $j$ 时，坐标小于 $j$ 的区间已经得到的最大总代价，则

$$dp_j=\max\left(0,\max_{i<j}\{dp_i+p_iS(i,j)\}\right).$$

最终答案为 $dp_{m+1}$。

做法

子任务 1：枚举激活集合

枚举 $m$ 个点的全部子集。对每个区间从右向左找到最右激活点并累加其权值，取所有集合中的最大值。该做法直接按照定义计算，复杂度为 $O(2^m(n+m))$。

子任务 2：二次动态规划

从左到右枚举前一个被选点 $i$。先按左端点加入所有满足 $l\le i$ 的区间，再向右扫描 $j=i+1,i+2,\ldots,m+1$，按右端点累计 $S(i,j)$，用上式更新 $dp_j$。

每个 $i$ 的扫描为 $O(m)$，加上区间预处理，总复杂度为 $O(n+m^2)$，空间复杂度为 $O(n+m)$。

满分算法：带后缀坐标平移的李超线段树

把每个已处理的点 $i$ 看成一条直线

$$f_i(x)=p_ix+dp_i.$$

若能让查询位置 $j$ 对应的横坐标等于 $S(i,j)$，则转移就是查询这些直线的最大值。扫描点坐标时，一个区间只会在其左端点和右端点后一位产生事件；这些事件对一段连续后缀的横坐标统一加一或减一。

使用一棵李超线段树维护以下操作：

1. 插入一条直线；
2. 查询某个叶子的最大函数值；
3. 将某个叶子后缀的横坐标统一平移。

线段树结点记录所覆盖叶子的左右横坐标、当前最优直线与懒标记。整段横坐标增加 $d$ 时，对已经存在的直线把截距减去 $kd$，便可保持这些直线在各叶子上的函数值不变；之后插入的新直线则会使用更新后的横坐标。部分覆盖时，把结点直线下放到两个儿子，再递归处理后缀。一次后缀平移访问 $O(\log m)$ 个结点，每次下放至多进行 $O(\log m)$ 的李超插入，因此耗时 $O(\log^2m)$。

扫描到坐标 $i$ 时，先查询得到 $dp_i$；随后处理所有左端点为 $i$ 的区间以及所有右端点加一等于 $i$ 的区间所对应的后缀平移，最后插入斜率 $p_i$、截距 $dp_i$ 的直线。对哨兵 $m+1$ 做同样查询，其值即为答案。

另写一份使用不同结点结构与下放顺序的李超线段树实现，对全部正式数据独立复算；小规模数据还与子集枚举和二次动态规划交叉验证。

复杂度

子集枚举的时间复杂度为 $O(2^m(n+m))$。二次动态规划的时间复杂度为 $O(n+m^2)$，空间复杂度为 $O(n+m)$。

满分算法的时间复杂度为 $O((n+m)\log^2m)$，空间复杂度为 $O(n+m)$。

正确性证明

对任意激活集合，在相邻激活点 $i<j$ 之间，恰有满足 $l\le i\le r<j$ 的区间以 $i$ 为最右激活点，其总贡献为 $p_iS(i,j)$。所以动态规划转移完整枚举了最后两个相邻激活点；反过来，每条转移对应把 $j$ 接在某个合法激活序列末尾，不会重复或遗漏，故 $dp_{m+1}$ 等于最优答案。

李超线段树始终保存每个已处理状态 $i$ 的函数 $p_ix+dp_i$。区间端点事件对后缀横坐标的平移恰好维护了计数 $S(i,j)$；平移时同步修正旧直线截距，只改变后续插入状态所看到的计数，而保持旧状态的既有函数值。由扫描顺序归纳，每次点查询得到的最大值正是动态规划转移式，因此优化算法与二次动态规划等价，答案正确。