c - 查询后在每个索引处查找最小值

Question

假设给你一个已知长度的数组 N它被初始化为无穷大。

(L,R,Val) 形式的查询被激活使得0 <= L <= R <= N-1 。每个查询都会更新数组，使得

for all i in [L, R]
  array[i] = min(Val, array[i])

例如:

初始化:N = 5 - 数组是 {inf, inf, inf, inf, inf}

查询 1:(1, 3, 6) - 数组转换为 {inf, 6, 6, 6, inf} .
查询2:(2, 4, 2) - 数组转换为 {inf, 6, 2, 2, 2} .

要求:完成所有查询后，找到每个元素索引处的值。

考虑上面名称为 arr 的数组，然后 - arr[0] = inf , arr[1] = 6 , arr[2] = 2 ...

针对这个问题，我有以下想法:

1. 暴力方法(获取每个查询并更新数组)。

2. 线段树(带或不带延迟传播)。

有没有其他方法可以解决这个问题(例如借助 sqrt 分解或使用其他数据结构，如堆栈或队列)来线性地或以更好的复杂度来解决它。

Answer 1

是的，你可以通过这种方式解决这个问题。
事件是由 bool 开始/结束、值和坐标组成的结构
每个查询都会转换为两个事件。例如，查询 L:1 R:5 VAL: 10 在事件 TRUE 10 1 和事件 FALSE 10 5 中进行转换
比按坐标值对所有事件进行排序
接下来遍历事件并保持当前最小值并填充数组
你可以用很多不同的数据结构来维护最少的内容(例如你可以在CPP中使用map)

该解决方案的复杂度为 O(M log M+(N+M) log M)其中 M 是查询数量，N 是元素数量