题目描述

难度分:$1600$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$，下标从$1$ 开始。然后输入$q(1 \leq n \leq 2 \times 10^5)$和$q$个操作。

有两种操作：

• 1 p x：将$a[p]$变为$x$。
• 2 x：将所有小于$x$的数变为$x$。
  其中$0 \leq x \leq 10^9$。

输出所有操作完成后的数组$a$。

输入样例$1$

4
1 2 3 4
3
2 3
1 2 2
2 1

输出样例$1$

3 2 3 4 

输入样例$2$

5
3 50 2 1 10
3
1 2 0
2 8
1 3 20

输出样例$2$

8 8 20 8 10 

算法

分类讨论

可以很容易发现的是，每进行一次操作$2$，数组$a$的最小值要么不变，要么就会变成$x$。因此，所有元素分为以下两种情况：

1. 如果$a[i]$没有进行过操作$1$，那它最终的值就是$max(a[i],x_{max})$，$x_{max}$是所有操作$2$中最大的那个$x$。
2. 如果$a[i]$进行过操作$1$，假设对$a[i]$最后一次操作$1$的操作编号为$t[i]$，那么只需要检查晚于$t[i]$的操作$2$中，有没有比$a[i]$大的$x$。有的话$a[i]$的值就是在这之后的操作$2$中$x$的最大值（$x$不超过$a[i]$时，$a[i]$保持最后一次操作$1$的值，不改变）；没有的话，$a[i]$保持最后一次操作$1$的值不变。

因此在进行$q$次操作时，对于操作$1$直接在数组上修改，并记录此时的$t[p]=i$。对于操作$2$，将（操作编号，$x$值）存入到二元组数组$modify$中。$q$次操作完成后，求$modify$第二关键字的后缀最大值数组$sufmax$。有了$modify$和$sufmax$两个数组，就能快速确定某个经历过操作$1$的位置$i$应该输出的值。

复杂度分析

时间复杂度

预处理出$modify$和$sufmax$的时间复杂度为$O(q)$；输出最终数组时，对于经历过操作$1$的$a[i]$，需要二分查找$modify$中第一个操作时间晚于$t[i]$的操作$modify[j].first$，然后输出$max(a[i],sufmax[j])$（$j$不存在就输出$a[i]$），因此时间复杂度为$O(nlog_2n)$。

综上所述，算法整体的时间复杂度为$O(q+nlog_2n)$。

空间复杂度

$modify$、$sufmax$和$t$三个辅助数组分别为$O(q)$、$O(q)$和$O(n)$的规模，因此算法整体的额外空间复杂度为$O(n+q)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int, int> PII;

const int N = 200010;
int n, q, a[N], t[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        t[i] = 0;
    }
    int mn = *min_element(a + 1, a + n + 1);
    scanf("%d", &q);
    int mx = mn, tmx = 0;    // mx是所有操作中x的最大值，也是所有操作完成后数组a对应的最小值，tmx是mx出现时的操作编号
    vector<PII> modify;
    for(int i = 1; i <= q; i++) {
        int tp;
        scanf("%d", &tp);
        if(tp == 1) {
            int p, x;
            scanf("%d%d", &p, &x);
            a[p] = x;
            t[p] = i;
            if(x < mn) {
                mn = x;
            }
        }else {
            int x;
            scanf("%d", &x);
            if(x >= mx) {
                // 此时数组的最小值会改变为x
                tmx = i;
                mx = x;
            }
            modify.push_back({i, x});
        }
    }
    int sz = modify.size();
    vector<int> sufmax(sz);
    if(sz > 0) {
        sufmax[sz - 1] = modify[sz - 1].second;
        for(int i = sz - 2; i >= 0; i--) {
            sufmax[i] = max(sufmax[i + 1], modify[i].second);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(t[i] == 0) {
            // a[i]没有被指定操作过
            printf("%d ", max(mx, a[i]));
        }else {
            int l = 0, r = sz - 1, j = -1;
            while(l <= r) {
                int mid = l + r >> 1;
                if(modify[mid].first > t[i]) {
                    j = mid;
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(j == -1) {
                printf("%d ", a[i]);
            }else {
                printf("%d ", max(a[i], sufmax[j]));
            }
        }
    }
    puts("");
    return 0;
}