[APIO2016] 划艇
注意到 \(n\le 500\) 考虑 \(O(n^3)\) 的做法。
值域小的做法比较显然，值域比较大，考虑离散化（ 将 \(b_i+1\) 然后限制变为 \([a_i,b_i+1)\) ）。
设 \(f_{i,j}\) 表示考虑前 \(i\) 个，\(i\) 选择 \(j\) 的方案数。
发现由于离散化了很难转移 \(f_{k,j}\ (k<i)\) 的情况，但由于单调性，只要前面选择了第 \(j\) 块后面都只能选择第 \(j\) 块，前面的直接乘上小于 \(j\) 的方案和就好的，那么问题转移到求解一个矩形内的子问题，并且这个矩形宽是 \(O(n)\) 级别，长是 \(O(v)\) 级别的。
考虑如何快速求解这个子问题
先考虑 DP 去做，则 DP 定义同上（ 只不过是没有离散化的 ）
设 \(s_{i,j}=\sum_{x\le i,y\le j}f_{x,y}\)，则有转移 \(f_{i,j}=1+s_{i-1,j-1}\)。
这个 \(s\) 数组有些烦人，考虑去掉，注意到 \(f\) 数组本质上就是一个前缀和的形式
考虑二维前缀和容斥，则有 \(f_{i,j}=(f_{i-1,j}-1)+(f_{i,j-1}-1)-(f_{i-1,j-1}-1)+f_{i-1,j-1}+1\)
上式化简得 \(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)，其中 \(f_{1,1}=1\)。
是否觉得这个东西有些熟悉？
竟然是矩形路径数！
那么我们就能得到 \(f\) 数组的封闭形式，即 \(f_{i,j}=\binom{i+j-2}{i-1}\)，能 \(O(n)\) 求解。
设这个矩形的宽为 \(i\)，长为 \(v\)，则这个子问题的答案则为 \(\sum_{j=1}^{v}f_{i,j}=\sum_{j=1}^v\binom{i+j-2}{i-1}=\binom{i+v-1}{i}\)。
那么我们就能 \(O(n)\) 求解这个子问题，并且因为转移得遍历前继所有包含 \(j\) 这一块的所以能倒序递推，这样复杂度就是对的了，但由于子问题的答案起始点是不定的，所以得简单容斥去重。
复杂度为 \(O(n^3)\)。
标签：动态,题解,sum,离散,le,考虑,矩形,规划,binom From： https://www.cnblogs.com/07Qyun/p/18521988