algorithm - 解决这个问题的最佳方法是什么？

Question

我在一次在线编码竞赛中看到了这个编码问题，但我找不到最佳解决方案。这是一个问题：
“给定一个包含 N 个整数和 Q 个查询的数组 A。每个查询具有以下类型：
1 pos val：将索引 pos 处的元素更新为 val
2 pos：找到 i 小于或的最小索引等于 pos 使得 i 和 pos 之间的所有元素都相同。”

我以某种方式相信我们可以使用段树，但我无法弄清楚段树的每个索引将代表什么。

Answer 1

这是 O(N + Q log^2 N) 方法：

1. 为给定数组构建段树
2. 在每个段树节点中存储间隔的最小数量和间隔中的最大数量
3. 现在可以通过对分段树的简单更新来完成类型 1 的查询
4. 对于类型 2 的查询，我们可以使用二进制搜索来找到最小的 i，使得 range[i, pos] 中的最小值等于同一范围内的最大值