251119D. mod
维护一个小根堆，有两种操作共 \(n\) 次，
- 在 \([l_i,r_i]\) 中均匀随机一个整数 \(x\)，插入小根堆。
- 弹出最小值。
问最终剩下的所有数的积的期望。
下文中，当值相同时令更早的数更小，这样就不用考虑重值的问题。
考虑在一个数加入的时候就确定它最终是否被弹出。
一个数 \(x\) 能合法地确定为被保留，当且仅当不存在一个数 \(y>x\) 且确定为被弹出，否则 \(x\) 总会在 \(y\) 前被弹出。
一个数 \(x\) 能合法地确定为被弹出，当且仅当不存在一个数 \(y\le x\) 且确定为为保留，否则 \(y\) 总会在 \(x\) 前被弹出。
由此不难设计出一个 DP 状态。\(f(i,k,l,r)\) 表示执行完前 \(i\) 个操作，有 \(k\) 个数确定被弹出，这 \(k\) 个数中的最大值为 \(l\)，其余被保留的数中最小值为 \(r\)。
对于操作 \(1\)，枚举范围内每一个 \(x\)。然后讨论 \(x\) 与 \(l,r\) 的大小关系：
- \(x<l\)，\(f(i,k,l,r)\rightarrow f(i+1,k+1,l,r)\)。
- \(x\ge r\)，\(f(i,k,l,r)\times x\rightarrow f(i+1,k,l,r)\)。
- \(l\le x<r\)，\(f(i,k,l,r)\rightarrow f(i+1,k+1,x,r)\) 或者 \(f(i,k,l,r)\times x\rightarrow f(i+1,k,l,x)\)。
对于操作 \(2\)，将所有 \(k=0\) 的状态丢弃，然后对于其余的 \(k\)：
- \(k\ge 2\)，\(f(i,k,l,r)\rightarrow f(i,k-1,l,r)\)。
- \(k=1\)，\(f(i,1,l,r)\rightarrow f(i,0,0,r)\)。
\(k=1\) 的转移是因为 \(k=0\) 时没有数将要被弹出，即其中最大值为 \(0\)。
由此可以获得一个 \(O(n^2V^3)\) 的做法，其中 \(V\) 是值域。
在转移的过程中，\(r\) 是单调不增的，从一个 \(k=0\) 到下一个的过程中，\(l\) 是单调不降的。同时还有 \(l\le r\) 恒成立。
（图中绿色线表示 \(l\)，红色线表示 \(r\)，淡蓝色竖线表示 \(k=0\) 的时刻。
因此我们可以将原来的 \(l,r\) 的状态用图中的橙色横线 \(y=t\) 来表示。但是这样可能被算重，因为存在多条可能的橙色线满足 \(l\le t\le r\)。因此可以额外添加一个条件，要求 \(t=r\)，即值为 \(t\) 的数至少被保留一次。也就是图中紫色线的状态。
由此可以设计出新的 DP 状态：\(f(i,k,t,0/1)\) 表示考虑完前 \(i\) 次操作，还有 \(k\) 个数没有弹出，值为 \(t\) 的数是否被保留过。
对于 \(1\) 操作，可以按照 \(x\) 与 \(t\) 的大小关系转移。
对于 \(2\) 操作，\(k\ge 2\) 直接，对于 \(k=1\)，\(f(i,1,t,1)\rightarrow f(i+1,1,t,1)\) 或者 \(f(i+1,1,<t,0)\)。
直接做到 \(\mathcal O(n^2V^2)\)，前缀和优化转移做到 \(\mathcal O(n^2V)\)。