There is a country with ??n citizens. The ??i-th of them initially has ????ai money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.
Sometimes the government makes payouts to the poor: all citizens who have strictly less money than ??x are paid accordingly so that after the payout they have exactly ??x money. In this case the citizens don‘t send a receipt.
You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.
The first line contains a single integer ??n (1≤??≤2⋅1051≤n≤2⋅105) — the numer of citizens.
The next line contains ??n integers ??1a1, ??2a2, ..., ????an (0≤????≤1090≤ai≤109) — the initial balances of citizens.
The next line contains a single integer ??q (1≤??≤2⋅1051≤q≤2⋅105) — the number of events.
Each of the next ??q lines contains a single event. The events are given in chronological order.
Each event is described as either 1 p x (1≤??≤??1≤p≤n, 0≤??≤1090≤x≤109), or 2 x (0≤??≤1090≤x≤109). In the first case we have a receipt that the balance of the ??p-th person becomes equal to ??x. In the second case we have a payoff with parameter ??x.
Print ??n integers — the balances of all citizens after all events.
4 1 2 3 4 3 2 3 1 2 2 2 1
3 2 3 4
5 3 50 2 1 10 3 1 2 0 2 8 1 3 20
8 8 20 8 10
In the first example the balances change as follows: 1 2 3 4 →→ 3 3 3 4 →→ 3 2 3 4 →→ 3 2 3 4
In the second example the balances change as follows: 3 50 2 1 10 →→ 3 0 2 1 10 →→ 8 8 8 8 10 →→ 8 8 20 8 10
哭了哭了~~
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=200010; int a[maxn],last[maxn],b[maxn];//a为原数组,last[i]记录修改i节点的最后一个位置,b[i]代表从i时间点往后最大的补充x值 int main() { int n,q; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>q; for(int i=1;i<=q;i++){ int op,x,y; cin>>op; if(op==1){ cin>>x>>y; a[x]=y;//修改原数组值 last[x]=i;//记录修改x下标的最后一个位置i } else{ cin>>b[i];//输入i时间点的补充值b[i] } } for(int i=q-1;i>=0;i--)b[i]=max(b[i],b[i+1]); for(int i=1;i<=n;i++)cout<<max(a[i],b[last[i]])<<" "; cout<<endl; return 0; }
原文：https://www.cnblogs.com/cherish-lin/p/11273959.html