20230629习题总结-526互联

考虑每个数正负状态的贡献，维护优先级后缀最小值。多项式部分不清晰。

因为有重复的价格，贪心不成立，考虑反悔，反悔时不直接删去而是加入一个可撤销的等价于返回的操作，便于反悔之前的反悔。

两个区间要么无交要么严格包含，可以建树，一个区间父亲为最小的严格包含它的区间。树形 dp 解决。
sol

必有一个学校的被选课程质量和大于其总质量和的一半。枚举这个学校，找到必选点，对于另一个学校，枚举右端点，用线段树维护每个左端点的答案，右端点更新时用单调栈求出影响区间并更改。

问题可以转化为构造矩阵对 \({A,B}\)，使得 \(B\) 的每行每列最大值不大于 \(A\) 的同行同列最小值的方案数。