题目大意

给定一个长度为 $n$ 的颜色序列，每个位置有一个颜色值。有 $m$ 次查询，每次查询区间 $[l, r]$，问将该区间涂成目标颜色所需的最少笔数。涂色规则：

• 一次操作可以涂一段连续区间
• 只能在浅色上覆盖深色（即颜色值大的可以覆盖颜色值小的）

关键思路

核心观察

对于区间 $[l, r]$ 内的涂色，最少笔数等于区间中所有"必须新起一笔"的位置个数。

什么情况下必须新起一笔？

• 位置 $i$ 是区间中第一个出现的某种颜色
• 或者更准确地说：如果 $i$ 左边没有比 $a[i]$ 更小的颜色，那么 $i$ 就需要新起一笔

算法核心

1. 单调栈预处理：维护一个递增单调栈，找到每个位置左边第一个比它小的颜色位置
2. 贡献计算：对于位置 $i$，如果栈顶元素颜色与 $a[i]$ 相同，说明可以用同一笔覆盖；否则需要新起一笔
3. 树状数组维护：用树状数组记录每个位置作为起点的贡献，支持区间查询

主要流程

1. 离线处理：将所有查询按右端点排序

2. 单调栈维护：

   while (topf && a[stk[topf]] > a[i]) --topf;
   

   维护栈的单调递增性

3. 贡献更新：

   • 如果栈顶颜色与当前相同：add(stk[topf] + 1, 1)
   • 否则：add(1, 1)
   • 同时 add(i + 1, -1) 确保区间完整性

4. 查询回答：

   for (auto [l, id] : q[i])
       ans[id] = ask(l);
   

复杂度分析

• 时间复杂度：$O((n + m) \log n)$
  • 单调栈：$O(n)$
  • 树状数组操作：$O(n \log n)$
  • 查询处理：$O(m \log n)$
• 空间复杂度：$O(n + m)$

总结

本题将涂色笔数问题转化为区间内特定位置的计数问题，通过单调栈+树状数组+离线查询的组合，高效解决了大规模数据下的区间查询问题。