对于一个固定的右端点\(r\)，左端点\(l\)合法当且仅当\(\max(d_l,d_{l+1},\dotsd_r)\ler-l+1\le\min(c_l,c_{l+1},\dots,c_r)\)。容易得到一个很朴素的dp：记\(f_i\)表示前\(i\)个位置可以分成的组的数目的最大值，\(g_i\)表示有多少种分组方案能达到最大值，直接枚举左端点

思维妙妙题。首先发现\(d\)的限制满足单调性，所以可以转化为\(l\gep_r\)的限制。注意：\(p\)是单调不降的然后就是\(p_r\lel\ler,\max\limits_{i=l}^r\{c_i\}\ler-l+1\)。这个\(\max\)想到转化到笛卡尔树上操作。然而这题要需要一个dp，所以考虑类似cdq分治一样

简要题意有\(n\)个人，把他们划分成尽可能多的区间，其中第\(i\)个人要求它所在的区间长度大于等于\(c_i\)，小于等于\(d_i\)，求最多的区间数量以及如此划分的方案数。数

[PA2014]Kuglarz题目描述魔术师的桌子上有\(n\)个杯子排成一行，编号为\(1,2,…,n\)，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费

  我们用一个数列\(\{a_n\}\)来表示这些杯子，\(a_n=1\)表示第\(n\)个杯子下藏有小球，\(a_n=0\)表示没有。那么第\([l,r]\)个杯子底下藏有球的总数的奇偶性就可以用