P7416 [USACO21FEB] No Time to Dry P 题解

link T4，虽然说难度像S组T3。

一排 $n$ 个格子，第 $i$ 个格子需要染成颜色 $a_i$。

每轮操作：选择一个区间 $[l, r]$ 和一个颜色 $c$，将该区间所有格子染成 $c$。
染色需满足：若格子当前颜色为 $x$，新颜色 $y$ 必须满足 $y \ge x$。

$q$ 次询问，每次给出区间 $[l_i, r_i]$，求只对该区间内格子染成目标颜色的最小操作轮数。

$1\leq n,q\leq 5\times 10^5$

---

考虑如何能节省使用染料的次数：如果前面有与当前染料相同的颜色，并且这俩之间的所有颜色都比这俩大，那么就可以一起染色，减小次数。

那么我们可以从左往右扫，扫到 $i$ 时，维护 $b_j$ 表示此时 $[j,i]$ 区间的结果。离线询问将答案存下来。

从 $i-1$ 更新到 $i$ 时，令 $pre_i$ 表示与 $c_i$ 相同的上一个位置。

如果条件成立，那么所有的 $b_{j\in [1,pre_i]}$ 都可以获得减免。

至于 $j\in (pre_i,i]$，由于没有了前面的染料，因此这个区间内的 $b_j$ 都无法获得减免。

如果条件不成立，显然直接给所有 $b_{j\in [1,i]}$ +1 即可。

那么就需要预处理相同的颜色、维护区间最小值、区间加单点查询。

分别用离散化、ST 表、树状数组/线段树维护即可。

补铁代马。

sub