There is a country with nn citizens. The ii-th of them initially has aiai 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 xx are paid accordingly so that after the payout they have exactly xx 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 nn (1≤n≤2⋅1051≤n≤2⋅105) — the numer of citizens.
The next line contains nn integers a1a1, a2a2, ..., anan (0≤ai≤1090≤ai≤109) — the initial balances of citizens.
The next line contains a single integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of events.
Each of the next qq lines contains a single event. The events are given in chronological order.
Each event is described as either 1 p x (1≤p≤n1≤p≤n, 0≤x≤1090≤x≤109), or 2 x (0≤x≤1090≤x≤109). In the first case we have a receipt that the balance of the pp-th person becomes equal to xx. In the second case we have a payoff with parameter xx.
Print nn 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;
const int maxx = 4e5;
int a[maxx],v[maxx],t[maxx];
int main()
{
int n,k,m,x,y,maxx = -1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>k;
if(k==1)
{
cin>>x>>y;
a[x] = y;
t[x] = i;//
}
else{
cin>>x;
v[i] = x;
}
}
for(int i=m-1;i>=0;i--)
{
v[i] = max(v[i+1],v[i]);
}
for(int i=1;i<=n;i++)
{
cout<<max(a[i],v[t[i]])<<" ";
}
cout<<endl;
return 0;
}
1.给一个区间[L,R] 加上一个数x
2.把一个区间[L,R] 里小于x 的数变成x
3.把一个区间[L,R] 里大于x 的数变成x
4.求区间[L,R] 的和
5.求区间[L,R] 的最大值
6.求区间[L,R] 的最小值
#include <cstdio>#include <algorithm>#define N 2000010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long long ll;const int inf = 1 << 30;int mx[N] , cx[N] , sx[N] , mn[N] , cn[N] , sn[N] , add[N];ll sum[N];inline void pushup(int x){int ls = x << 1 , rs = x << 1 | 1;sum[x] = sum[ls] + sum[rs];if(mx[ls] > mx[rs]) mx[x] = mx[ls] , cx[x] = cx[ls] , sx[x] = max(sx[ls] , mx[rs]);if(mx[ls] < mx[rs]) mx[x] = mx[rs] , cx[x] = cx[rs] , sx[x] = max(mx[ls] , sx[rs]);if(mx[ls] == mx[rs]) mx[x] = mx[ls] , cx[x] = cx[ls] + cx[rs] , sx[x] = max(sx[ls] , sx[rs]);if(mn[ls] < mn[rs]) mn[x] = mn[ls] , cn[x] = cn[ls] , sn[x] = min(sn[ls] , mn[rs]);if(mn[ls] > mn[rs]) mn[x] = mn[rs] , cn[x] = cn[rs] , sn[x] = min(mn[ls] , sn[rs]);if(mn[ls] == mn[rs]) mn[x] = mn[ls] , cn[x] = cn[ls] + cn[rs] , sn[x] = min(sn[ls] , sn[rs]);}inline void pushdown(int l , int r , int x){int ls = x << 1 , rs = x << 1 | 1;if(add[x]){int mid = (l + r) >> 1;mx[ls] += add[x] , sx[ls] += add[x] , mn[ls] += add[x] , sn[ls] += add[x] , sum[ls] += (mid - l + 1) * add[x] , add[ls] += add[x];mx[rs] += add[x] , sx[rs] += add[x] , mn[rs] += add[x] , sn[rs] += add[x] , sum[rs] += (r - mid) * add[x] , add[rs] += add[x];add[x] = 0;}if(mx[ls] > mx[x]){if(mn[ls] == mx[ls]) mn[ls] = mx[x];if(sn[ls] == mx[ls]) sn[ls] = mx[x];sum[ls] += 1ll * (mx[x] - mx[ls]) * cx[ls] , mx[ls] = mx[x];}if(mx[rs] > mx[x]){if(mn[rs] == mx[rs]) mn[rs] = mx[x];if(sn[rs] == mx[rs]) sn[rs] = mx[x];sum[rs] += 1ll * (mx[x] - mx[rs]) * cx[rs] , mx[rs] = mx[x];}if(mn[ls] < mn[x]){if(mx[ls] == mn[ls]) mx[ls] = mn[x];if(sx[ls] == mn[ls]) sx[ls] = mn[x];sum[ls] += 1ll * (mn[x] - mn[ls]) * cn[ls] , mn[ls] = mn[x];}if(mn[rs] < mn[x]){if(mx[rs] == mn[rs]) mx[rs] = mn[x];if(sx[rs] == mn[rs]) sx[rs] = mn[x];sum[rs] += 1ll * (mn[x] - mn[rs]) * cn[rs] , mn[rs] = mn[x];}}void build(int l , int r , int x){if(l == r){scanf("%lld" , &sum[x]) , mx[x] = mn[x] = sum[x] , cx[x] = cn[x] = 1 , sx[x] = -inf , sn[x] = inf;return;}int mid = (l + r) >> 1;build(lson) , build(rson);pushup(x);}void vadd(int b , int e , int a , int l , int r , int x){if(b <= l && r <= e){mx[x] += a , sx[x] += a , mn[x] += a , sn[x] += a , sum[x] += 1ll * (r - l + 1) * a , add[x] += a;return;}pushdown(l , r , x);int mid = (l + r) >> 1;if(b <= mid) vadd(b , e , a , lson);if(e > mid) vadd(b , e , a , rson);pushup(x);}void vmax(int b , int e , int a , int l , int r , int x){if(mn[x] >= a) return;if(b <= l && r <= e && sn[x] > a){if(mx[x] == mn[x]) mx[x] = a;if(sx[x] == mn[x]) sx[x] = a;sum[x] += 1ll * (a - mn[x]) * cn[x] , mn[x] = a;return;}pushdown(l , r , x);int mid = (l + r) >> 1;if(b <= mid) vmax(b , e , a , lson);if(e > mid) vmax(b , e , a , rson);pushup(x);}void vmin(int b , int e , int a , int l , int r , int x){if(mx[x] <= a) return;if(b <= l && r <= e && sx[x] < a){if(mn[x] == mx[x]) mn[x] = a;if(sn[x] == mx[x]) sn[x] = a;sum[x] += 1ll * (a - mx[x]) * cx[x] , mx[x] = a;return;}pushdown(l , r , x);int mid = (l + r) >> 1;if(b <= mid) vmin(b , e , a , lson);if(e > mid) vmin(b , e , a , rson);pushup(x);}ll qsum(int b , int e , int l , int r , int x){if(b <= l && r <= e) return sum[x];pushdown(l , r , x);int mid = (l + r) >> 1; ll ans = 0;if(b <= mid) ans += qsum(b , e , lson);if(e > mid) ans += qsum(b , e , rson);return ans;}int qmax(int b , int e , int l , int r , int x){if(b <= l && r <= e) return mx[x];pushdown(l , r , x);int mid = (l + r) >> 1 , ans = -inf;if(b <= mid) ans = max(ans , qmax(b , e , lson));if(e > mid) ans = max(ans , qmax(b , e , rson));return ans;}int qmin(int b , int e , int l , int r , int x){if(b <= l && r <= e) return mn[x];pushdown(l , r , x);int mid = (l + r) >> 1 , ans = inf;if(b <= mid) ans = min(ans , qmin(b , e , lson));if(e > mid) ans = min(ans , qmin(b , e , rson));return ans;}int main(){int n , m , opt , x , y , z;scanf("%d" , &n);build(1 , n , 1);scanf("%d" , &m);while(m -- ){scanf("%d%d%d" , &opt , &x , &y);if(opt == 1) scanf("%d" , &z) , vadd(x , y , z , 1 , n , 1);if(opt == 2) scanf("%d" , &z) , vmax(x , y , z , 1 , n , 1);if(opt == 3) scanf("%d" , &z) , vmin(x , y , z , 1 , n , 1);if(opt == 4) printf("%lld\n" , qsum(x , y , 1 , n , 1));if(opt == 5) printf("%d\n" , qmax(x , y , 1 , n , 1));if(opt == 6) printf("%d\n" , qmin(x , y , 1 , n , 1));}return 0;}
京公网安备 11010502036488号