单调队列+treap
会爆栈，要c++扩栈。
题意：给出n个数(n<=10^5),给出m，要求将数列分成连续的若干段，使得每段之和<=m，且每段中的最大值的和最小，求这个最小的和
分析：
很容易得到：dp[i]=min{dp[j]+max{a[j+1……i]}|bound[i]<=j<=i-1},其中bound[i]是使得sigma(a[j+1]……a[i])<=m的最大下标，可以二分得到。
状态数O(n),转移O(n)，显然要优化。
由于bound[i]是随着i的增大单调不降的，而且一个点j要成为i的最优决策首先必须满足a[j]比a[j+1……i]都要大(这点还不明白)。那么我们可以用单调队列维护。
现在对于确定的决策j，我们可以O(1)时间知道a[j+1]~a[i]的最大值(若q[p]=a[j]，那么max{a[j+1]~a[i]}=q[p+1]，q[p+1]存在的前提下)，但是对于状态i，当前单调队列的队首元素的原始下标不一定就是最优决策值，所以我们要找到一种数据结构动态的维护dp[j]+max{a[j+1]~a[i]},其中a[j]是当前单调队列中的元素。那么显然当状态转移的时候需要对这种数据结构插入、删除、求最小值。显然这种数据结构应当是平衡树为好。
思路还是很清晰的，但是要注意细节，队列中的元素个数要时刻清晰，插入删除了哪些决策下的答案要清楚。还有就是对于决策是bound这种情况，要特判。因为我代码里面的单调队列都是从bound+1开始的元素。