题目链接

题目描述

有一个初始长度为 $n(1 \le n \le 10^5)$ 的序列 $a$

有 $m(1 \le m \le 5 \times 10^6)$ 次操作,每次给定 $l,r,k$,将 $\forall i \in [l,r]$,把 $a_i$ 变为 $\max(a_i,k)$

求最终的序列 $a$

题解

首先多次区间查询最大值是和这个问题等价的

那么就把操作反向过来,每次相当于在 $ST$ 表上打上标记,最终反着跑一遍 $ST$ 表