题意：
一共有 nnn 天，大 Y 可以花费 ddd 的能量在任何一天跑步，但大 Y 不能在连续的 kkk 天跑步。
此外，将给出 mmm 段任务区间 [li,ri][l_i,r_i][li ,ri ]。如果在这段区间的每一天都跑了步，则会获得 viv_ivi 的能量。
大 Y 的初始能量为 000，请你最大化跑完步后大 Y 最终的能量。
思路：
有一个最朴素的状态设计方案就是 fif_ifi 表示考虑前 iii 天并且第 iii 天跑步的最大能量值 ，然后定义 gi=maxj=1ifjg_i = \max\limits_{j=1}^{i}f_{j}gi =j=1maxi fj
转移方程：
fi=maxj=i−k+1 i{gj−2−(i−j+1)⋅d+∑[lp,rp]⊆[j,i]vp}f_i = \max_{j=i-k + 1}^{\,i} \left\{ g_{j-2} -(i-j + 1)\cdot d + \sum_{[l_p,r_p]\subseteq [j,i]} v_p \right\} fi =j=i−k+1maxi ⎩⎨⎧ gj−2 −(i−j+1)⋅d+[lp ,rp ]⊆[j,i]∑ vp ⎭⎬⎫
这样子直接暴力转移的时间复杂度是O(nmk)O(nmk)O(nmk)的。
可以想到，对于枚举的区间 [j,i][j,i][j,i]，能够贡献答案的任务区间 [lk,rk][l_k,r_k][lk ,rk ] 一定满足j≤lk≤rk≤ij\le l_k\le r_k\le ij≤lk ≤rk ≤i。
现在我们将区间 [li,ri][l_i,r_i][li ,ri ] 看作是二位平面上的点 (ri,li)(r_i,l_i)(ri ,li ) , 那么我们就能把后面的暴力求和变成求解二维平面上矩形的点权和，于是乎变成了一个基础的二维数点问题。
那么我们按照右端点顺序把任务区间加入，则 rk≤ir_k\le irk ≤i 的条件就能天然满足。计算贡献时，我们就只需要查询满足 lk≥jl_k\ge jlk ≥j 的任务区间的权值和即可，这个可以用树状数组维护，单次计算贡献的复杂度降至 O(logm)O(\log m)O(logm)，整体时间复杂度O(nklogm)O(nklog_{m})O(nklogm )
接下来考虑优化 nnn ，由于最终的得分和完成的任务以及跑步的时间有关，因此会发现在一个区间开始或结束的时间开始跑步是一定不劣的，在一个区间的结束的时间完成跑步也一定不劣。因此我们的决策点就只有每个任务的 li,ril_i , r_ili ,ri 两个点，这样就可以大大的减少状态数量，时间复杂度也就成了 O(mklogm)O(mklog_m)O(mklogm ) ，这就是通过最优性质来保留一定不劣的点，减少状态数。
最后，还剩下一个瓶颈没有解决：对于每一个端点都要枚举前 kkk 个。所以我们需要接着优化 dpdpdp 转移
转移为
dpi=max1≤j≤ipi−pj+1≤k{gpre(j)+gain(i,j)−cost(i,j)}.dp_i = \max_{\substack{1\le j\le i\\ p_i-p_j+1\le k}} \left\{ g_{\mathrm{pre}(j)} +\text{gain}(i,j) -\text{cost}(i,j) \right\}. dpi =1≤j≤ipi −pj +1≤k max {gpre(j) +gain(i,j)−cost(i,j)}.
另外，由于相邻关键天数之间可能存在空档天，需要区分“pj−1p_{j-1}pj−1 与 pjp_jpj 是否相邻”：
pre(j)={j−2,j≥2 且 pj=pj−1+1,j−1,否则.\mathrm{pre}(j)= \begin{cases} j-2, & j\ge 2\ \text{且}\ p_j=p_{j-1}+1,\\ j-1, & \text{否则}. \end{cases} pre(j)={j−2,j−1, j≥2 且 pj =pj−1 +1,否则.
最后有
gi=max(gi−1,dpi).g_i=\max(g_{i-1},dp_i). gi =max(gi−1 ,dpi ).
接下来我们考虑从 i→i+1i \to i+1i→i+1的过程中，每个决策点的 gpre(j)g_{pre(j)}gpre(j) 不变，cost(i,j)cost(i,j)cost(i,j) 变化量一样，gain(i,j)gain(i,j)gain(i,j) 的变化量取决于 jjj 的大小，也就是说实际上这是一个区间修改+区间查询的问题，很自然想到用线段树来维护每个决策点 gpre(j)+gain(i,j)−cost(i,j)g_{pre(j)} + gain(i,j) - cost(i,j)gpre(j) +gain(i,j)−cost(i,j)
的取值，然后在进行区间查询最值即可，查询范围可以双指针快速解决。时间复杂度为O(mlogm)O(mlog_m)O(mlogm )
