【代码源 Div1 - 107】#452. 序列操作（思维）CF1198B

problem

solution

• 注意到操作2是全局的，而且所有操作是离线的，所以可以记录操作 2 修改后的最大值，
• 再开个 vis 数组记录当前的数是否被操作 1 修改过，然后反向暴力一遍。

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

#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 1e6+10;

int a[maxn], vis[maxn];
tuple<int,int,int>op[maxn];

int main(){
    IOS;
    int n, q;  cin>>n>>q;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= q; i++){
        int x, y, z;  cin>>x>>y;
        if(x==1)cin>>z;
        op[i] = {x,y,z};
    }
    int mx = 0;
    for(int i = q; i >= 1; i--){
        if(get<0>(op[i]) == 2){
            mx = max(mx, get<1>(op[i]));
        }else if(vis[ get<1>(op[i]) ] == 0){
            vis[get<1>(op[i])] = 1;
            a[get<1>(op[i])] = max(mx, get<2>(op[i]) );
        }
    }
    for(int i = 1; i <= n; i++){
        if(vis[i])cout<<a[i];
        else cout<<max(mx, a[i]);
        cout<<" \n"[i==n];
    }
    return 0;
}