题目分析

本题要求实现一个数据结构，支持一种复合操作：

区间查询与赋值：查询区间 $[l, r]$ 内等于 $c$ 的元素个数，然后将整个区间内的元素都设置为 $c$

算法设计

本题的特殊之处在于操作同时包含查询和修改，而且修改操作是将整个区间设置为同一个值。这种操作具有"覆盖"特性，可以利用这一特性进行优化。

分块算法与标记优化

我们采用分块算法，并为每个块维护以下信息：

统一赋值标记 (tag)：如果整个块的值相同，则记录这个值

块内数据：当块内元素不完全相同时，存储实际数据

核心思想

如果一个块被统一赋值过，那么整个块的值都是 tag

查询时，如果块有统一标记且标记值等于 $c$，则整个块都计数

修改时，如果整个块都在操作区间内，直接设置统一标记

算法复杂度分析

时间复杂度

查询与设置操作：

最坏情况：$O(\sqrt{n})$（需要处理多个不完整块）

平均情况：$O(\sqrt{n})$（得益于统一标记优化）

下放标记：$O(\text{块大小}) = O(\sqrt{n})$

检查统一性：$O(\text{块大小}) = O(\sqrt{n})$

空间复杂度

$O(n)$：存储数组和标记信息

关键优化点

统一标记系统：

记录整个块是否具有相同的值

避免对统一块进行不必要的遍历

懒标记技术：

只在需要时下放标记

减少不必要的数组更新

操作合并：

查询和修改在一次遍历中完成

减少重复遍历的开销

自动统一检测：

操作后检查块是否变得统一

为后续操作提供优化机会

性能分析

最坏情况 当每次操作都跨越多个不完整块且没有统一标记时，需要遍历所有相关元素，复杂度为 $O(\sqrt{n})$

最佳情况 当操作覆盖完整块且这些块都有统一标记时，只需要检查标记值，复杂度为 $O(1)$ 每个块

平均情况 在随机数据下，统一标记会逐渐形成，后续操作复杂度降低

扩展思考

这种"查询+覆盖"的操作模式在实际应用中很常见，比如：

图像处理中的区域填充

文档编辑中的格式刷

数据库中的批量更新

统一标记的思想可以推广到其他具有"局部一致性"特征的问题中。

代码总结

本题展示了一种高效处理"查询+覆盖"操作的分块算法。通过统一标记系统和懒标记技术，算法在保持简单性的同时达到了较好的性能。

核心技巧：

利用操作特性进行针对性优化

统一标记减少重复计算

懒标记延迟实际更新

操作合并提高效率

这种设计模式在需要处理批量更新和查询的问题中具有很好的参考价值。