cdq 分治 + 线段树.
设 $f(i)$ 表示前 $i$ 个人能分成的组数最大值,转移有,
$$
f(i)=\max_{j=0}^{i-1} \lbrace f(j) \rbrace +1 ,\max c\le i-j \le \min d
$$
其中, $\max c$ 表示区间 $[j+1,i]$ 内最大的 $c$ , $\min d$ 表示区间 $[j+1,i]$ 内最小的 $d$ .
$d$ 的限制是容易处理的,若只考虑 $d$ 的限制,对于每个 $i$ ,合法的 $j$ 显然是一段后缀,设为 $[g(i),i-1]$ .
而 $g(i)$ 是不降的,可以用双指针扫,每次用线段树问一下区间最小的 $d$ ,就能在 $O(n\log n)$ 的时间内预处理出来.
要加上 $c$ 的限制,考虑 cdq 分治,要算出 $[l,r]$ 内的每个 $f(i)$ ,若 $l=r$ ,就返回.
否则,先取划分位置 $k$ 表示区间 $[l+1,r]$ 内 $c$ 最大的位置.
递归处理 $[l,k-1]$ 后,考虑 $[l,k-1]$ 的 $dp$ 值对 $[k,r]$ 的贡献,再递归处理 $[k,r]$ .
在区间 $[k,r]$ 内依次枚举 $i$ ,计算左边区间对右边区间每个 $i$ 的贡献,并且时刻维护合法的 $j$ 中, $f(j)$ 的最大值.
初始时,合法的 $j$ 所在区间为 $[\max(l,g(i)),\min(k-1,i-c_k)]$ .
每当 $i$ 往右边移动一个位置,当 $i< k+c_k$ 时, $j$ 所在区间右端点也会往右边移动一个位置,直接把它的贡献加入.
而 $j$ 所在区间左端点也可能往右边移动,由于不支持删除一段区间的贡献,只能用线段树重新查询一次.
当 $i$ 移动到 $k+c_k$ 时,右端点不再移动,而左端点单调不降,每次二分出左端点相同的一段 $i$ ,用线段树一起更新答案.
计算贡献的同时还要计算方案数,可以定义一个二元组 $(mx,cnt)$ ,一起转移即可.
这样计算,时间复杂度 $T(n)=T(x)+T(n-x)+\min(x,n-x)$ ,为 $O(n\log n)$ .
如果我们对于每个 $i$ ,都对合法的 $j$ 所在区间用线段树查询一次,由于划分位置不一定是区间中点,就退化了.
1 | //%std |