$T3$ 题意理解错了.直接爆炸.
$sequence$
- 考虑一段区间 $[l,r]$ 合法,则显然 $\forall\ l\leq i\leq r,b_i\geq \max_{j=l}^i a_j$ .
- 这个东西对于 $l,r$ 两边来说都是具有单调性的, $two\ pointer$ 扫一遍即可.
- 用线段树做 $RMQ$ 为 $O(nlogn)$ ,用 $ST$ 表则为 $O(n)$ .
$circulate$
- 考虑枚举循环节循环次数,对于每个确定的循环次数,二分出循环节数字的最大值.
- 为了计算不重不漏,容斥一下,该循环次数的质因子个数为奇数,则加上,否则减去.
$2\times 10^{18}$ 有 $19$ 个数字…考试没加 $19$ 的情况,丢了 $20$ 分.
$cannon$
- 题意搞错了,没注意到一座山被轰了几次后高度减低,可以换其他的炮轰…
- $80pts$ 很简单.设 $f(i)$ 表示轰平一座高度为 $i$ 的山最少需要轰几次,然后从低到高判断能否轰即可.
- 转移就有 $\forall x\leq 0,f(x)=0.f(i)=1+f(i-max_D)$ , $max_D$ 表示 $A_j\geq i$ 中最大的 $D_j$ .
- $100pts$ 的做法就是在上面改一下.因为 $D\leq 300$ ,所以上面的 $f$ 数组有用的只有 $M\cdot D$ 个.用 $map$ 做即可.