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;
}