发现自己的码力还是太弱,可能需要多做毒瘤题(?)
$cubicp$
$P=a^3-b^3=(a-b)(a^2+ab+b^2)$ ,因为 $P$ 是质数,所以 $a-b=1$ .
于是 $P=3b^2+3b+1$ ,先预处理所有合法的答案,然后快速回答即可.
$dp$
考虑朴素的 $dp$ ,设 $f(i,j)$ 表示将前 $i$ 个数分成 $j$ 段的最小花费.
先枚举 $j$ ,可以发现 $i$ 的转移决策是具有单调性的,于是可以优化.
不能用二分决策栈的方法,因为转移额外代价 $cost(k,i)$ 不方便快速在线算.
对求解区间和决策区间分治,这样可以像莫队那样暴力移动端点来算 $cost$ ,时间复杂度 $O(n\log n)$ .
$number$
可以先二分答案 $mid$ ,于是要考虑 $1\sim mid$ 的全部区间.将它们按照 $x$ 从大到小排序,依次加入.
如果同一种 $x$ 的区间的交集被之前加入的所有区间的并集完全覆盖,显然就不合法,否则一定可以构造出合法的方案.
可以直接用线段树来维护区间覆盖,但会多一个 $\log$ .
优秀的做法是用并查集维护当前每个节点在并集中向右能跳到的最远点,就可以判断合法性了.