神仙DP题。
题意：给出两个长度为 $n$ 的数列 $c$ 和 $d$ ，让你将 $1$ 至 $n$ 分为连续的几段，保证每段长度 $L$ 满足对于每个属于该区间的元素 $i$ ， $\max(c_i)\leq L\leq\min(d_i)$ 。问最多分几组，有几种分法能使组数最多，方案数对 $10^9+7$ 取模。
$1\leq n\leq 10^6$
考虑朴素 $n^2$ DP。
设 $f[i]$ 为前 $i$ 个最多能分 $f[i]$ 组，则转移方程 $f[i]=\max(f[j-1])+1,j\in [1,i], \max(c_j,c_{j+1},\ldots,c_i)\leq i-j+1 \leq \min(d_j,d_{j+1},\ldots,d_i)$
考虑如何优化。
令 $\rm maxC(j,i)$ 表示 $\max(c_j,c_{j+1},\ldots,c_i)$ ， $\rm minD(j,i)$ 表示 $\min(d_j,d_{j+1},\ldots,d_i)$ 。
$\rm maxC(j,i)\leq i-j+1\leq \rm minD(j,i)$
$i-\rm minD(j,i)+1\leq j\leq i-\rm maxC(j,i)+1$
对于左端点 $i-\rm minD(j,i)+1$ ，当 $i$ 不断加大时，易证（不会证感性理解也能出来）左端点只会加大不会减小，具有单调性。因此可以用尺取法（或其他方法）求出对于每一个 $i$ ，能转移到 $i$ 的 $j$ 的左端点为常数，记为 $\rm L_i$ 。
然后考虑右端点，不具有单调性。
由于对于每个 $i$ ，影响其转移右端点的关键因素就是 $maxC(j,i)$ ，所以进行分治。
$solve(l,r)$ 先在区间 $[l,r]$ 中找出 $k$ 使 $c_k$ 最大，然后递归 $solve(l,k-1)$ ，转移， $solve(k,r)$ 。
对于当前正在处理的 $solve(l,r)$ ，只考虑左区间 $j\in [l,k-1]$ 对右区间 $i\in [k,r]$ 的转移。此时 $\rm maxC(j,i)$ 为常数 $c_k$ ，记 $c_k+1$ 为 $\rm K$ 。
此时对于 $i\in [k,r]$ ，其转移区间为 $[\max(l,\rm L_i),\min(r,i-\rm K)]$ 。若这个区间为空，则直接跳过。
当 $i$ 递增时， $\rm L_i$ 递增， $i-\rm K$ 也递增。所以 $i-\rm K<l$ 或 $k-1<\rm L_i$ （即区间为空）的 $i$ 只出现在右区间两端，此时无需转移。我们只要考虑转移区间不为空的 $i$ 即可。
同样的，当 $\rm L_i$ 递增时， $i$ 也在递增。
我们将i分为两个部分： $\rm L_i\leq l$ 和 $l<\rm L_i$ 。
对于前者，我们只需对 $f$ 建立线段树，然后在线段树上查询第一个 $i$ 的答案。后面的每个 $i$ 只会右移 $\min(k-1,i-\rm K)$ 一次， $O(1)$ 暴力维护即可（怎么 $O(1)$ ？动动你的小脑浆好好想想）。而且不难发现当 $k-1\leq i-\rm K$ 后，所有 $i$ 的转移区间都是一样的，我们可以直接用线段树区间取 $\max$ 完成转移。复杂度 $\log n+\min(k-l,r-k+1)$
对于后者，我们只要在线段树上暴力查询即可。这时肯定会有人出来问我，这复杂度好像不太对啊，成 $log^2$ 了。但实际上，复杂度是均摊 $log$ 的。证明很简单：
对于每个 $i$ ，只有一个 $\rm L_i$ 。对于每一个 $i\in [k,r]$ 的分治层，其 $[l,k-1]$ 的交为空集，并为整个 $[1,i-1]$ 。故 $l<\rm L_i\leq k-1$ 的情况对于每个 $i$ 最多只会出现一次，每次复杂度为 $\log n$ ，总复杂度 $n\log n$ 。
再分析分治复杂度， $T(a+b)=T(a)+T(b)+\min(a,b)+\log n=\rm O(n\log n)$
完美。
不过要注意，此题卡空间，所以各种空间复杂度比较高的数据结构（如ST表）可以用其他空间比较优秀的数据结构代替，用时间换空间。
代码没写，反正卡空间的题写了也会很丑。