题面描述：

给定 $n$ 个数 $A_1, A_2, ..., A_n$ 和 $m$ 个操作，操作分为两个类型：

① 给出 $p,x$，将第 $A_p$ 修改为 $x$；

② 给出 $x$，将整个序列中小于 $x$ 的数替换成 $x.$

求最后所有数的值。

$1 \le n,m \le 2*10^5, 0 \le x,A_i \le 10^9$

解析

分析题目，可以发现有几个性质：

• 同一个单点修改只需要记录最后一次
• 当一个数最后一次单点修改以后，答案只会受区间修改的影响

所以，我们用一个数组 $b$ 记录，$b_i$ 代表第 $i$ 个数最后一次修改（单点）是第几次操作。

因为 $A$ 数组执行单点修改不影响效率，所以我们单点修改值替换直接在数组 $A$ 上进行。

另外，我们使用数组 $c$，$c_i$ 记录第 $i$ 次到第 $m$ 次区间修改操作的最大值。

为什么要这么做呢？

我们之前定义了一个数组 $b$，那么 $c_{b_i}$ 就是除了单点修改所得的答案了。

输出的时候，第 $i$ 个数的答案就是 $\max(A_i,c_{b_i})$

怎么求出各个变量

数组 $A$：只需要支持单点修改，因此 $O(n)$ ；

数组 $b$：对于每一次的单点操作，都要更新当前点的最后一次出现，所以递推一遍，复杂度 $O(n).$

数组 $c$：先储存区间修改操作的记录，再后缀递推答案，复杂度 $O(n).$

参考代码

// 上文数组 A 即 a，数组 b 即 l，数组 c 即 b #include 
     
      inline int read(){    int num = 0, b = 1;    char c = getchar();    while(c < '0' || c > '9'){        if(c == '-') b = -1;        c = getchar();    }    while(c >= '0' && c <= '9'){        num = num * 10 + c - '0';        c = getchar();    }    return num * b;}int n, a[200010], l[200010], q, opt, x, y;int b[200010];inline int max(int a, int b){    return a > b ? a : b;}int main(){        n = read();    for(int i=1; i<=n; i++)        a[i] = read();            q = read();    for(int i=1; i<=q; i++){        opt = read();        if(opt == 1){            x = read(), y = read();            a[x] = y;            l[x] = i;        }        else{            x = read();            b[i] = x;        }    }        for(int i=q-1; i>=0; i--)        b[i] = max(b[i], b[i + 1]);        for(int i=1; i<=n; i++)        printf("%d ", max(a[i], b[l[i]]));    return 0;}