序列操作

题目描述：

给你一个长度为n的序列，有两种操作：

• 1 x y 将第x个数字改成y
• 2 y 将所有小于y的数字改成y

进行q次操作，输出执行完所有操作后序列

思路：

对于操作1，显然对于同一个位置，只有最后一次修改的是有意义的，在最后一次修改之前进行的任何操作都不会影响他的值

对于操作2，显然一个数字会覆盖掉前面出现的所有小于他的数字的影响，同时也会覆盖掉后面出现的所有小于他的数字的影响，所以如果不存在操作1的时候，每个数字都会变成max(tr[i], ma)，ma为操作2的最大值，但是由于存在操作1的单点修改，操作一的对象x只会受到在x后面的操作2的影响，所以需要计算是后缀的操作2的最大值

所以我们考虑离线，逆序遍历所有操作，对于操作2，我们可以维护一个maxn表示到目前为止出现的操作2的最大值，对于操作1，我们开一个vis数组来维护这个数字被修改了没有

• 操作1：如果当前这个数字没有被修改过，我们就给ans[i]记录答案，ans[i]=max(maxn, y),同时更新一下标记
• 操作2：我们更新maxn就行

最后统计答案的时候，我们从头遍历一遍序列，如果这个数字的vis=1,说明这个位置是存在操作1的，则的答案已经确定了，如果vis=0则答案还没有确定下来，则答案就是max(maxn, tr[i])

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m, k, x;
int tr[MAX];
struct ran{
    int op, x, y;
}ar[MAX];
bool vis[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= m; ++i){
        cin >> ar[i].op >> ar[i].x;
        if(ar[i].op == 1)cin>>ar[i].y;
    }
    int maxn = 0;
    for(int i = m; i >= 1; --i){
        if(ar[i].op == 1 && vis[ar[i].x] == 0){
            vis[ar[i].x] = 1;
            tr[ar[i].x] = max(maxn, ar[i].y);
        }
        else if(ar[i].op == 2)maxn = max(maxn, ar[i].x);
    }
    for(int i = 1; i <= n; ++i)if(!vis[i])tr[i] = max(tr[i], maxn);
    for(int i = 1; i <= n; ++i)cout << tr[i] << ' ';
    cout << endl;
}


int main(){
    io;
    work();
    return 0;
}